目录

70. 爬楼梯 （进阶）

思路

爬楼梯

1或2步爬楼梯

多步爬楼梯

322. 零钱兑换

思考

1、确定dp数组及其含义

2、确定递推公式

3、初始化dp数组

4、确定遍历顺序

零钱兑换

先遍历物品，再遍历背包

先遍历背包，再遍历物品

279.完全平方数

思路

完全平方数

创建完全平方和数组，套用公式

将完全平方和融入到公式中

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的完全平方数的最少数量是0for (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的完全平方数的最少数量是0for (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];}
}