1. 爬楼梯（进阶版）

算法思路

1. 1阶，2阶，.... m阶就是物品，有 j 阶台阶的楼顶就是背包；
2. 采用完全背包问题解决。

注意点

1. dp[0]要初始化为1，因为既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了；
2. 爬楼梯求最多方法问题也是一个排列问题，要先遍历背包。

代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        // 数爬到有j个台阶的楼顶，有dp[j]种方法
        int[] dp = new int[n+1];
        dp[0] = 1;
        
        for(int j = 1; j<=n; j++){
            for(int i = 1; i<= m; i++){
                if(j>=i) dp[j] += dp[j-i];
            }
        }
        
        System.out.println(dp[n]);
    }
}

2. 零钱兑换

算法思路

1. 本题求的是凑成目标金额的所需的最少硬币数目，而不是方法个数，所以不涉及顺序问题；
2. 采用完全背包的套路来做即可。

注意点

1. 如果 dp[j - coins[i]] 等于 max：这意味着到目前为止，还没有找到任何一种硬币组合能够凑成金额 j - coins[i]。那么即便再加上当前的硬币 coins[i]，也无法从一个不可行的状态得到一个可行的凑成金额 j 的方案。所以只有在dp[j - coins[i]] 不等于 max，选择 i 才有意义；
2. 如果dp[amount]最后等于max, 则说明凑不出来。

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        // 凑成金额为j的最少硬币数为dp[j]
        int[] dp = new int[amount+1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for(int i = 0; i<coins.length; i++){
            for(int j = coins[i]; j<=amount; j++){
                if(dp[j-coins[i]] != max){
                    dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
                }
                
            }
        }

        return dp[amount] == max? -1 : dp[amount] ;
        
    }
}

3. 完全平方数

算法思路

与零钱兑换非常相似，但是此题没有“凑不成”的情况。

注意点

1. 因为 j 的遍历应该从1开始，所以i可以从 1 开始取；
2. 因为题目里没有提到从0开始取，所以dp[0]初始化为0；
3. 在完全平方数这题中不存在凑不成这种情况。

代码

class Solution {
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        // 和为j的完全平方数的最小数量为dp[j]
        int[] dp = new int[n+1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for(int i = 1; i*i<=n; i++){
            for(int j = i*i; j<=n; j++){
                if(dp[j-i*i] != max){
                    dp[j] = Math.min(dp[j], dp[j-i*i]+1);
                }
            }
        }

        return dp[n];
        
    }
}

4. 单词拆分

算法思路

1. 确定dp[i] 的状态，并截取字符串中 j-i 的部分。
2. 如果确定dp[i] 是true，且 [i, j] 这个区间的子串出现在字典里，那么dp[j]一定是true。

注意点

判断是否包含函数contains()，字符串截取函数substring()的拼写；

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        // 长度为j的字符串是否能够被拼接而成
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int j = 1; j<=s.length(); j++){
            for(int i = 0; i<j; i++){
                if(words.contains(s.substring(i, j)) && dp[i]){
                    dp[j] = true;
                }
            }
        }

        return dp[s.length()];
        
    }
}