第45天 Dynamic Programming 完全背包 70、322、279

30. Climbing Stairs

除了Fibonacci数列，还可以转化为完全背包 背包容量：n即楼梯个数 物品数量：2，这道题只能爬1阶楼梯，或者2阶楼梯 物品重量：1或2 dp[j]: 凑满j的排列数

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int j=0; j<=n; j++) {
            for (int i=1; i<=2; i++) {
                if (j >= i) dp[j] += dp[j-i];
            }
        }
        return dp[n];
    }
}

322. Coin Change

dp[j]: 凑足总额为j所需钱币的最少个数为dp[j] 公式：dp[j] = Math.min(dp[j], dp[j-coins[i]]+1); 初始化：因为需要凑足，比如coins=[2], amount=3, return -1，所以初始化时，除了dp[0]=0，其他都是凑不足的（0个数可以凑成0，但是0个数不能凑成1or2or3） 本来我初始化为-1，但是因为递推公式设计Math.min，-1会带来很多不便 代码随想录初始化为Integer.MAX_VALUE; if (dp[j-coins[i]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j-coins[i]]+1); if (dp[j] != -1 && dp[j-coins[i]] != -1) dp[j] = Math.min(dp[j], dp[j-coins[i]]+1); else if (dp[j] == -1 && dp[j-coins[i]] != -1) dp[j] = dp[j-coins[i]]+1; 遍历顺序：本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的 注意要考虑dp[j-coins[i]]是否可以凑足，如果dp[j-coins[i]]凑不足，没有更新的必要，dp[j]也凑不足

// Integer.MAX_VALUE
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i=0; i<coins.length; i++) {
            for (int j=coins[i]; j<=amount; j++) {
                if (dp[j-coins[i]] != Integer.MAX_VALUE) 
                    dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

// -1
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i=0; i<coins.length; i++) {
            for (int j=coins[i]; j<=amount; j++) {
                if (dp[j] != -1 && dp[j-coins[i]] != -1) 
                    dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
                else if (dp[j] == -1 && dp[j-coins[i]] != -1)
                    dp[j] = dp[j-coins[i]]+1;
            }
        }
        return dp[amount];
    }
}

279. Perfect Squares

dp[j]: 和为j的完全平方数的最少数量为dp[j] 公式：dp[j] = Math.min(dp[j], dp[j-i*i]+1); 初始化：一定要dp[0]=0，不然会初始化成最大值。非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。 不像coin change需要考虑dp[j-i*i] != Integer.MAX_VALUE，因为一定有1可以凑成任何数

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i=1; i*i<=n; i++) {
            for (int j=i*i; j<=n; j++) {
                // if (dp[j-i*i] != Integer.MAX_VALUE) 
                    dp[j] = Math.min(dp[j], dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}