LC 518 Coin Change 2(M)

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000 1 <= coin <= 5000 the number of coins is less than 500 the answer is guaranteed to fit into signed 32-bit integer

边界条件 如果 amount = 0, 直接返回1

解题思路 DP

用coin值为间隔距离， dp[a] = dp[a] + dp[a-coin] 累计每个amount点的组合值， 和 322 coin change 有类似的思路。

public int change(int amount, int[] coins) {
    if (amount == 0) return 1;
    //保存每个amount点的组合值
    int[]dp = new int[amount + 1];

    for(int coin: coins){
        if (coin > amount) continue;
        // 直接给 amount =  coin 的加一
        dp[coin]++;
        // amount从coin + 1 开始, 当前值dp[a] 加上 相隔 coin value 的dp[a-coin]的组合值。
        for(int a = coin + 1; a <= amount; a++){
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}
优化后算法 - 利用dp[0] 
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i-coin];
        }
    }
    return dp[amount];
}