518. 零钱兑换 II (opens new window)

1.动规+完全背包

dp二维背包表示考虑前i种物品，价值金额为j的方案总数。细节如下：

• 完全背包问题每种硬币可以取多次，因此顺序遍历，并且使用第i种硬币的方案数应该是考虑前 i 种硬币下金额达到j-coins[i-1]的方案数，而不能是前i-1种的结果dp[i-1][j-coins[i-1]](导致第i种硬币只会使用一次)。
• 如果不想预处理i=0时添加硬币coints[0]的情况，那么dp第一维的大小可以扩大1，从i=1开始放入计算第一个硬币的数目。
• dp[i][0]=1作为 j=coins[i-1]的哨兵节点。

class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp=new int[coins.length+1][amount+1];
        for(int i=1;i<=coins.length;i++){
            dp[i][0]=1;
            for(int j=1;j<=amount;j++){
                dp[i][j]+=dp[i-1][j];
                if(j-coins[i-1]>=0) dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[coins.length][amount];
    }
}

2.一维空间优化

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int i=1;i<=coins.length;i++){
            for(int j=1;j<=amount;j++){
                if(j-coins[i-1]>=0) dp[j]+=dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
}