70. 爬楼梯 （进阶）
题目链接：力扣
思路
在使用动态规划解决爬楼梯问题的时候，从到达一个台阶有多少种方式入手，使用动态规划是可以很好的解决
学了完全背包后，可以从另一个角度分析这道题目
物品：每次可以爬1个台阶、每次可以爬2个台阶
拿取：可以重复拿取步数
背包：n阶台阶数
求值：求的是有多少种方法爬到楼顶（排列数）
这样看起来，这个题目的内容就和求排列数一样了
和 377. 组合总和Ⅳ 一样了
求排列数的注意内容：
1、初始化dp[0] = 1
2、遍历时，先遍历背包，再遍历物品
3、递推公式为 dp[j] = dp[j-weigth[i]]
多步爬楼梯问题：
假设你正在爬楼梯，需要跨过m个台阶才能到达楼顶。每一步你可以跨过1个台阶、2个台阶、3个台阶……m个台阶，直到n层台阶，你有多少种方法可以爬到楼顶呢
多部爬楼梯解决：
按照上面的思路，如果每次爬楼梯的步数是 1 或者 2，那么物品的数组就是【1，2】
如果每次爬楼梯的步数是 1、2、3……m,那么物品的数组就是【1，2，3……m】
爬楼梯
1或2步爬楼梯
// 创建步数数组 class Solution { public int climbStairs(int n) { // 物品数组 int[] nums = new int[]{1,2}; // 创建dp数组 int[] dp = new int[n+1]; // 初始化dp数组 dp[0] = 1; // 填充dp数组 for (int j = 1; j <= n; j++) { for (int i = 0; i < nums.length; i++) { if (j >= nums[i]) { dp[j] += dp[j-nums[i]]; } } } return dp[n]; } } // 不创建步数数组 class Solution { public int climbStairs(int n) { // 创建dp数组 int[] dp = new int[n+1]; // 初始化dp数组 dp[0] = 1; // 填充dp数组 for (int j = 1; j <= n; j++) { for (int i = 1; i <= 2; i++) { if (j >= i) { dp[j] += dp[j-i]; } } } return dp[n]; } }
多步爬楼梯
class Solution { public int climbStairs(int n) { // 创建dp数组 int[] dp = new int[n+1]; // 初始化dp数组 dp[0] = 1; // 填充dp数组 for (int j = 1; j <= n; j++) { // 遍历背包 for (int i = 1; i <= m; i++) { // 遍历步数，步数是从1开始的 if (j >= i) { dp[j] += dp[j-i]; } } } return dp[n]; } }
322. 零钱兑换
题目链接：力扣
思考
虽然已经做了几天的动态规划，但是每次再拿到动态规划的题目的时候思路还不是很清楚，主要就是如何定义dp[]数组，定义了dp[]数组之后怎么确定递推公式，确定了递推公式之后怎么对数组进行初始化，初始化之后使用那种遍历顺序
目前来说，定义dp[]数组，基本上都是题目要求什么就定义什么。主要有三类：
1、纯求背包中物品的价值：
这种就是一般的背包问题，是比较简单的一种
递推公式一般是：dp[ j ] = max(dp[ j ],dp[ j - weigth[ i ] ] + value[ i ]);
2、求物品装满背包的方法数
这种dp[]数组就是方法数，如果是完全背包，还可能牵扯组合数和排列数
递归公式一般是：dp[ j ] += dp[ j - weight[ i ] ]
由于方法数是逐步积累的，所以初始化应该是dp[ 0 ] = 1
3、求装满背包时，背包中的物品数
这种dp[]数组求得是最终背包中的物品个数
递推公式一般与dp[ j - weight[ i ] ] + 1 ) 有关
如果是求最大个数：就是dp[ j ] = max(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最大值，初始化时dp[0] = 0,其余的也为0。对应的题目有 474.一和零
如果是求最小个数：就是dp[ j ] = min(dp[ j ],dp[ j - weight[ i ] ] + 1 );由于是求最小值，初始化时dp[0] = 0,其余的为MAX_VALUE。对应的题目有 322.零钱兑换
下面对本题目进行动态五部曲的分析：
1、确定dp数组及其含义
题目求什么，就定义什么。题目要求的内容：计算并返回可以凑成总金额所需的 最少的硬币个数
dp[ j ]: 凑成总金额为 j 所需要硬币的最小个数
2、确定递推公式
确定好递推公式后，发现这是上面总结的第三类问题，是求背包中的物品个数，也就是和dp[ j - coins[ i ] ] + 1 ) 有关
如果说添加了当前物品（coins[i]），那么这个背包中的物品就需要进行添加，背包中的物品个数就是 dp[ j - coins[i] ] + 1
如果说没有添加当前物品（coins[i]）, 那么这个背包中的物品中的个数就不需要进行改变，背包中物品的个数就是 dp[ j ]
所以说dp[ j ] = min(dp[ j ],dp[ j - coins[ i ] ] + 1 )
3、初始化dp数组
凑足总金额为0 所需要硬币的个数一定是0，所以dp[0] = 0
其余的下标的元素必须初始化为一个最大值，否则 min(dp[ j ],dp[ j - coins[ i ] ] + 1 ) 计算出的值就被初始化的值覆盖掉了
4、确定遍历顺序
不强调组合和排列，先遍历背包或者先遍历物品都是可以的
零钱兑换
先遍历物品，再遍历背包
class Solution { public int coinChange(int[] coins, int amount) { // 创建dp数组 int[] dp = new int[amount + 1]; // 初始化dp数组 dp[0] = 0; for (int i = 1; i <= amount; i++) { dp[i] = Integer.MAX_VALUE; } // 遍历更新dp数组 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]; } }
先遍历背包，再遍历物品
class Solution { public int coinChange(int[] coins, int amount) { // 创建dp数组 int[] dp = new int[amount + 1]; // 初始化dp数组 dp[0] = 0; for (int i = 1; i <= amount; i++) { dp[i] = Integer.MAX_VALUE; } // 遍历更新dp数组 for (int j = 0; j <= amount; j++) { // 再遍历背包 for (int i = 0; i < coins.length; i++) { // 先遍历物品 if (j - coins[i] >=0 && 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]; } }
279.完全平方数
题目链接：力扣
思路
这道题和上面322.零钱兑换是一样的，只不过这道题目的物品数组没有明给，需要自己创建，说着直接套用到公式中
完全平方数
创建完全平方和数组，套用公式
class Solution { public int numSquares(int n) { // 首先要根据背包创建完全平方和数组 // 对 n 进行开平方 double lens = Math.sqrt(n); // 对开方出来的数组进行向上取整 int len = (int)Math.ceil(lens); // 创建物品数组 int[] nums = new int[len + 1]; // 遍历的时候从下标1开始 for (int i = 0; i <= len; i++) { nums[i] = i * i; } // 创建dp数组 int[] dp = new int[n + 1]; // 初始化dp数组 dp[0] = 0; // 和为0的完全平方数的最少数量是0 for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; //设置最大值，避免被覆盖 } // 遍历更新dp数组 for (int i = 1; i <= len; i++) { for (int j = nums[i]; j <= n; j++) { if (dp[j-nums[i]] != Integer.MAX_VALUE) { dp[j] = Math.min(dp[j],dp[j-nums[i]] + 1); } } } return dp[n]; } }
将完全平方和融入到公式中
class Solution { public int numSquares(int n) { // 创建dp数组 int[] dp = new int[n + 1]; // 初始化dp数组 dp[0] = 0; // 和为0的完全平方数的最少数量是0 for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; //设置最大值，避免被覆盖 } // 遍历更新dp数组 for (int i = 1; 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]; } }
139.单词拆分
题目链接：力扣
思路
比较直接的想法就是使用回溯法不断去组合字符串，比较组合出来的字符串是否与目标字符串相同，显然，回溯这种枚举的方法有很多无效功
将目标字符串看成背包，将集合中的单词看成物品，集合中的单词能不能组成目标字符串，就是问物品能不能把背包装满。集合中的字符串是可以重复使用的，说明这是一个完全背包问题
1、确定dp数组的含义
dp[i]:字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词
2、确定递推公式
i 是在遍历目标字符串
j 是每次从0开始遍历目标字符串
对于leetcode, i 遍历到4的时候，j 再对字符串从0遍历，判断s.substring(0,4) -- “leet”在 集合中是存在的，并且dp[0]是为true的，所以此时 下标4 位置上就可以设置为 true,代表leet 是存在在集合中的
下一次，i遍历到8的时候，j 再对字符串从0开始遍历，遍历到 j = 4的时候，判断s.substring(4,8) --"code" 在集合中是存在的，并且dp[4]是为true的，所以此时下标8位置上就可以设置成true,代表 code是存在在集合中的
其实本质上就是使用 true 对字符串进行了分割，如果分割到最后也是true,那就说明这个字符串是可以由集合中的元素组成的
所以判断该元素在集合中存在的条件是 set.contains(s.substring(j,i)) && dp[j]
3、dp数组如何初始化
从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了
4、确定遍历顺序
本题使用外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的
但本题还有特殊性，因为是要求子串，最好是遍历背包放在外循环，将遍历物品放在内循环
5、打印dp数组
单词拆分
class Solution { public boolean wordBreak(String s, List<String> wordDict) { HashSet<String> set = new HashSet<>(wordDict); // 创建dp数组 boolean[] dp = new boolean[s.length() + 1]; // 初始化dp数组 dp[0] = true; // 遍历填充dp数组 for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i && !dp[i]; j++) { if (set.contains(s.substring(j,i)) && dp[j]) { dp[i] = true; } } } return dp[s.length()]; } }
