Leetcode 518. 零钱兑换 II

使用该硬币时，可以选0个、1个、…、k个
上述状态转移方程可化简为：

class Solution {
public:
    int change(int amount, vector& coins) {
        int len = coins.size();

        vector> dp(len + 1, vector (amount + 1, 0));
        dp[0][0] = 1;

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

    }
};

class Solution {
public:
    int change(int amount, vector& coins) {
        int len = coins.size();

        vector dp(amount + 1, 0);
        dp[0]= 1;

        for (int i = 1; i <= len; i++) {
            int val = coins[i - 1];
            for (int j = val; j <= amount; j++) {
                dp[j] += dp[j - val];
            }
        }
        return dp[amount];

    }
};