Coin Change 2

题目来源
给一个钱数以及一些硬币，硬币可以无限取，问有多少种组合方案。
一看就是一道DP题，但是太久没刷题，手生。导致不会做==。
dp[i][j]表示只用前i种硬币，凑够数目j的组合数目。
则有dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0)。
代码如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n+1, vector<int>(amount+1, 0));
        dp[0][0] = 1;
        for (int i=1; i<=n; i++) {
            dp[i][0] = 1;
            for (int j=1; j<=amount; j++) {
                dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
            }
        }
        return dp[n][amount];
    }
};

然后可以将其简化为一维的，因为dp[i][j]只依赖于dp[i-1][j]和dp[i][j-coins[i-1]]，代码如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int i=coin; i<=amount; i++)
                //这里的dp[i-coin]实际上就是dp[i][j-coins[i-1]]，原dp[i]就是dp[i-1][j]
                dp[i] += dp[i-coin];   
        }
        return dp[amount];
    }
};