Leetcode-518. 零钱兑换 II

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

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10]
输出: 1
解题思路
完全背包问题
状态数组和basecase很好理解。注释有表标
递进关系：
如果容量不支持使用该硬币，则直接不适用，等于用前i-1个元素装
如果容量支持，则可装可不装。组合数相加。不装同上
装上时，我们可以只求装一次，那么组合数就为用前i个去装总容量-当前容量的子问题。
之所以是前i个，而不是前i-1个，就是因为第i个物品可以多次装载

class Solution {
    public int change(int amount, int[] coins) {
        int n=coins.length;
        //dp[i][j]表示用前i个面值的硬币可以凑出j总数的组合数
        int[][] dp=new int[n+1][amount+1];
        //base case:dp[0][...]:0--没有硬币，凑不出来---dp[...][0]=1---总数为0，不用凑为一种组合
        for(int i=0;i<=n;i++){
            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][j]=dp[i][j-coins[i-1]]+dp[i-1][j];
                }
            }
        }
        return dp[n][amount];
    }
}