Leetcode 518. 零钱兑换 II 动态规划
可参考官解:零钱兑换 II 和这个解答:[Java/Python3/C++]动态规划:拆分零钱兑换子问题(嵌套循环的秘密)【图解】
此题需要仔细想象和Leetcode 377. 组合总和 Ⅳ 动态规划的区别,本次是求组合数,是不考虑顺序的,Leetcode 377. 组合总和 Ⅳ 动态规划是求排列数,需要考虑顺序,因此答案更大。
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1,
0); // dp[i]表示凑成金额i的组合数,初始都为0表示不可凑
dp[0] = 1; // 金额0有一种组合方式,由0枚硬币组成
vector<int> can_change(amount + 1, 0);
can_change[0] = 1;
for (auto& c : coins) {
// 枚举每一个金额
for (int a = c; a <= amount; a++) {
can_change[a] |= can_change[a - c];
}
}
if (can_change[amount] == 0)
return 0;
// 枚举每一种硬币
// 先遍历所有硬币,再遍历金额数,这样会考虑使用硬币的顺序,不会出现先选1,再选2,和先选2再选1同时出现的情况
// 比如amount = 5, coins = [1, 2,
// 5],第一次外循环和内循环,就是计算,所有金额数只用coin=1组合得到的情况
// 第二次外循环和内循环,遍历在之前的金额数dp[i]的基础上,加上2得到当前金额数的可能,即先1后2的可能,不会再反复计算先2后1的可能
for (auto coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
};
// 5
// [1,2,5]
// 1
// dp[1]=0+dp[0]=1;
// dp[2]=0+dp[1]=1;
// dp[3]=0+dp[2]=1;
// dp[4]=0+dp[3]=1;
// dp[5]=0+dp[4]=1;
// 2
// dp[2]=1+dp[0]=2;
// dp[3]=1+dp[1]=2;
// dp[4]=1+dp[2]=3;
// dp[5]=1+dp[3]=3;
// 5
// dp[5]=3+dp[0]=4;
原文地址:https://blog.csdn.net/qq_45791939/article/details/145144872
免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!