【LeetCode-动态规划】零钱兑换 II

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例：

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

题目链接：

思路1

使用回溯来做。代码如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int ans = 0;
        int start = 0;
        int curMoney = 0;
        dfs(amount, start, coins, curMoney, ans);
        return ans;
    }

    void dfs(int amount, int start, vector<int> coins, int curMoney, int& ans){
        if(curMoney==amount){
            ans++;
            return;
        }
        if(curMoney>amount) return;

        for(int i=start; i<coins.size(); i++){
            curMoney += coins[i];
            dfs(amount, i, coins, curMoney, ans);
            curMoney -= coins[i];
        }
    }
};
// 超时

该方法超时未通过。

思路2

使用动态规划。

状态定义：dp[i][j] 表示使用前 i 个硬币组成金额 j 的组合数；
初始状态：dp[i][0] = 1，dp[0][j] = 0；
状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]，公式的含义就是第 i 个硬币不选还是选，也就是前 i 个硬币组成金额 j 的组合数等于前 i-1 个硬币组成金额 j 的组合数（不放第 i 个金币），加上前 i 个金币组成金额 j-coins[i-1] 的组合数（这种情况下再放一个金额为 coins[i-1] 的金币就行了）。代码如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> dp(coins.size()+1, vector<int>(amount+1, 0));

        for(int i=0; i<=coins.size(); i++){
            dp[i][0] = 1;
        }

        for(int i=1; i<=coins.size(); i++){
            for(int j=1; j<=amount; j++){
                if(j>=coins[i-1]) dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[coins.size()][amount];
    }
};

思路3

可以简化动态规划中的状态定义。

状态定义：dp[i] 代表使用第 k 个硬币能组成金额 i 的组合数；
状态转移方程：dp[i] = dp[i] + dp[i-k]，也就是放和不放第 k 个硬币两种情况；

代码如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;

        for(int i=0; i<coins.size(); i++){
            for(int j=1; j<=amount; j++){
                if(j>=coins[i]) dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

参考

1、https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/
2、https://leetcode-cn.com/problems/coin-change-2/solution/dp-wan-quan-bei-bao-ji-ben-zuo-fa-c-by-kiritoh/