自学内容网 自学内容网

Leetcode 518. 零钱兑换 II 动态规划

原题链接: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)!