518 coin change II （01背包）

https://leetcode.com/problems/coin-change-ii/

这里讲得更清楚，得仔细研究下，代表了一大类问题，细分包括物品可不可以重复，以及dp matrix的压缩

class Solution {
    public int change(int amount, int[] coins) {
        // dp[i]是amount为i的放法数量
        int[] dp = new int[amount+1];
        // 注意初始化
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            // 一定是正序遍历，这样之前得到的dp[j]值能累加到之后dp[j]上，也就保证了能重复拿无数个
            for (int j = coins[i]; j <= amount; j++) {
                // 其实是做了dp array的压缩，本应该是二维数组dp[i][j]表示拿了coin i的时候amount为j的放法
                // 本应该是dp[i][j] = dp[i-1][j](不拿这个硬币) + dp[i-1][j-coins[i]](拿这个硬币)
                //放法   //之前coin在相同amount下积累的放法
                dp[j] = dp[j] + dp[j-coins[i]];
                                //之前coin在去掉一个coins[i]之后积累的放法
                                //由于j在自增，所有j都减去了coins[i]，
                                //所以之后的j能累积到之前j使用了coins[i]的放法，保证了coin无限
                                //比如coin为1，那么j为1时放法加上了dp[1-1]=dp[0]=1，
                                //当j为2时放法中会加上dp[2-1]=dp[1]也就是j为1时候的放法，
                                //其中就包含了dp[1-1]的放法，依次累加下去
                                //如果用二维数组则不需要担心顺序问题
            }
        }
        return dp[amount];
    }
}

如果用二维做法是这样的

class Solution {
    public int change(int amount, int[] coins) {
        // dp[i][j]:使用硬币0-i时amount为j的放法
        int[][] dp = new int[coins.length][amount+1];
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1; // 容量为0的背包放法唯一(不放)
        }
        //只放硬币0时，amount==coins[0]倍数的时候放法为1，其余amount放法为0
        for (int j = 0; j <= amount; j++) {
            if (j % coins[0] == 0) {
                dp[0][j] = 1;
            }
        }
        for (int i = 1; i < coins.length; i++) {
            //注意这里从0开始，之所以一维时不用是因为一维天然继承上一次结果，现在如果不够用当前硬币我们要显式继承
            for (int j = 0; j <= amount; j++) {
                if (j < coins[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    //这里dp[i][j-coins[i]]天然包括了amount为j-coins[i]的时候使用coins[i]的情况
                    //所以不需要显式去把用一个两个三个coins[i]的情况加起来
                    // hint: 如果你希望不用重复使用，那么dp[i][j]=dp[i-1][j]+dp[i-1][j-coins[i]]
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];
                    //由于i和i-1互相不覆盖，所以不管j从大到小遍历还是从小到大都没关系
                }
            }
        }
        return dp[coins.length-1][amount];
    }
}