Leetcode-518:零钱兑换 II

题目描述：

思路：

类比零钱兑换第一题，每个面值的钱可以使用任意多次，我们可以构造一个dp数组，如dp数组的行数为N，列数为aim+1，dp[i][j] 的含义是：在可以任意使用arr[0..i]货币的情况下，组成钱数j有多少张方法。。

第一行dp[0][0..aim]中每一个元素dp[0][j]表示用arr[0]货币找开面额 j的方法，此时我们只能选取arr[0]这一张货币，所以只有arr[0]的整数倍的面额钱才可以找开，例如当arr[0]=3，aim=10时，只能找开3,6,9的货币，且只有一种方法即只是用arr[0]，而其他面额的则无法找开，所以将arr[0][3,6,9]初始化为1 除此之外其他值初始化为0表示无法找开。对于第一列dp[0..n][0] 中的每一个元素dp[i][0]表示用arr[i]组成面额为0的钱的最少货币数，完全不需要任何货币，即一种方法，初始化为1。

对于剩下的任意dp[i][j]，我们依次从左到右，从上到下计算，dp[i][j]的值下面的方法数的和：

• 完全不用arr[i]的货币，只使用arr[0..i-1]货币时，方法数为dp[i-1][j]
• 用1张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-arr[i]]
• 用2张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-2*arr[i]]
• …
• 用k张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-k*arr[i]]

其实从第二种情况到第k种情况方法的累加值其实就是dp[i][j-arr[i]]的值（解释一下：比如我们有两个硬币[1,2]，钱数为5，那么钱数的5的组成方法是可以看作两部分组成，一种是由硬币1单独组成，那么仅有一种情况(1+1+1+1+1)；另一种是由1和2共同组成，说明我们的组成方法中至少需要由一个2，所以此时我们先取出一个硬币2，那么我们只要拼出钱数为3即可，这个3还是可以用硬币1和2来拼，所以就相当于求由硬币[1,2]组成的钱数为3的总方法。），所以dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]] 。

代码：

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