导视设计网站,谷歌海外广告投放,上海民政网站相关建设情况,商丘市住房和城乡建设厅网站题目链接#xff1a;https://leetcode.cn/problems/coin-change/description/
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合…题目链接https://leetcode.cn/problems/coin-change/description/
给你一个整数数组 coins 表示不同面额的硬币以及一个整数amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1 示例 2
输入coins [2], amount 3 输出-1 示例 3
输入coins [1], amount 0 输出0
提示
1 coins.length 12
1 coins[i] 231 - 1
0 amount 104AC代码
#include iostream
#include vectorusing namespace std;int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, amount 1);dp[0] 0;for (int coin : coins) {for (int i coin; i amount; i) {dp[i] min(dp[i], dp[i - coin] 1);}}return dp[amount] amount ? -1 : dp[amount];
}int main() {vectorint coins {1, 2, 5};int amount 11;cout coinChange(coins, amount) endl;return 0;
}代码解释 这个C程序首先定义了一个动态规划数组dp其中dp[i]表示兑换i元所需的最少硬币数量。初始化时dp[0]被设置为0其他位置被设置为一个很大的数这里设置为amount 1。
然后程序遍历每个硬币对于每个硬币程序遍历从该硬币面值到amount的所有金额更新dp数组。具体来说对于每个金额i程序比较兑换i元所需的最少硬币数量和兑换i - coin元所需的最少硬币数量加上1即使用当前硬币取两者中的最小值。
最后程序返回dp[amount]即兑换amount元所需的最少硬币数量。如果dp[amount]大于amount则表示无法兑换返回-1。
