达州大亚网站建设,个人怎么做旅游网站,石家庄个人谁做网站,南通营销网站制作原题链接#xff1a;Leetcode 518. 零钱兑换 II 可参考官解#xff1a;零钱兑换 II 和这个解答#xff1a;[Java/Python3/C]动态规划#xff1a;拆分零钱兑换子问题#xff08;嵌套循环的秘密#xff09;【图解】
此题需要仔细想象和Leetcode 377. 组合总和 Ⅳ 动态规划…原题链接Leetcode 518. 零钱兑换 II 可参考官解零钱兑换 II 和这个解答[Java/Python3/C]动态规划拆分零钱兑换子问题嵌套循环的秘密【图解】
此题需要仔细想象和Leetcode 377. 组合总和 Ⅳ 动态规划的区别本次是求组合数是不考虑顺序的Leetcode 377. 组合总和 Ⅳ 动态规划是求排列数需要考虑顺序因此答案更大。
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1,0); // dp[i]表示凑成金额i的组合数初始都为0表示不可凑dp[0] 1; // 金额0有一种组合方式由0枚硬币组成vectorint 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]第一次外循环和内循环就是计算所有金额数只用coin1组合得到的情况// 第二次外循环和内循环遍历在之前的金额数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]0dp[0]1;
// dp[2]0dp[1]1;
// dp[3]0dp[2]1;
// dp[4]0dp[3]1;
// dp[5]0dp[4]1;// 2
// dp[2]1dp[0]2;
// dp[3]1dp[1]2;
// dp[4]1dp[2]3;
// dp[5]1dp[3]3;// 5
// dp[5]3dp[0]4;
