518. 零钱兑换 II（动态规划）

518. 零钱兑换 II

• 题目
• 解题思路
• 代码

题目

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

注意:

你可以假设：

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

解题思路

这是完全背包问题。

1. 背包问题，状态两种，不多说了。需要二维数组
2. dp数组含义也差不多。dp[i][j]:只使用前i个物品，当背包容量为j的时候，有dp[i][j]种凑法
3. base case也很相似，dp[0][...]=0、dp[..][0]=1不使用任何硬币，无法凑出任何金额。要凑的目标金额是0，就只有“无为而治”一种办法
4. 我们需要的dp就是dp[n][amount]，需要正向遍历
5. 也只有放入、不放入这两种选择，注意，放入的话状态转移方程是dp[i][j-coins[i-1]]。这是完全背包问题，所以是i 如果是0-1背包，那就是i-1
6. 我们求的是共有多少种凑法，所以应该是放入和不放入结果的和。而不是从其中选择一个。

代码

class Solution {
    public int change(int amount, int[] coins) {
        int n=coins.length;

        //dp[i][j]:只使用前i个物品，当背包容量为j的时候，有dp[i][j]种凑法
        int[][] dp=new int[n+1][amount+1];

        //base case
        for(int i=0;i<=n;i++){
            //要凑的目标金额是0，就只有“无为而治”一种办法
            dp[i][0]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=amount;j++){
                if(j-coins[i-1]<0){//背包满了
                    dp[i][j]=dp[i-1][j];
                }else{
                    //注意，本题是完全背包所以加入背包就是dp[i][...]。而0-1背包是dp[i-1][....]
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }
}