本文主要是介绍代码随想录算法训练营第四十五天| 70. 爬楼梯 （进阶），322. 零钱兑换 ，279.完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目与题解
70. 爬楼梯 （进阶）
题目链接：70. 爬楼梯 （进阶）
代码随想录题解：70. 爬楼梯 （进阶）
解题思路：
这道题要求每次可以爬1-m层的楼梯，最终爬到n，相当于完全背包问题中，有无限个重量为1-m的物品，每次可以取不同重量的物品，要求最后重量加起来等于n时有多少种排列。
那这题就跟组合总和IV是一样的了，就是完全背包+排列，因此for循环写的时候背包遍历在外侧，物品遍历在内侧，由于是完全背包问题，所以要从前往后遍历，递推公式求数目，那dp[i] += dp[i-j]即可。
import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[] dp = new int[n+1];dp[0] = 1;for (int i = 0; i <= n; i++) {for (int j = 1; j <= m && j <= i; j++) {dp[i] += dp[i - j];}}System.out.println(dp[n]);}
}看完代码随想录之后的想法
了解套路以后就可以套公式了
遇到的困难
虽然不是特别懂初始化要求、遍历顺序和遍历时究竟是物品在外面还是背包在外面，但是记住公式就能写。
322. 零钱兑换
题目链接：322. 零钱兑换
代码随想录题解：322. 零钱兑换
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili
解题思路：
硬币数量无限，求固定总和对应的最少硬币数目，实质上就是完全背包问题中的组合问题，不过，相比普通背包问题要求价值最大的物品组合，这里要求最少硬币数目，递推公式里面将用min而非max，所以对初始化有了一定要求，第一次没有写对。
看完代码随想录之后的想法
1. 确定dp数组以及下标的含义
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
2. 确定递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3.dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
4.确定遍历顺序
本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];Arrays.sort(coins);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);}}}if (dp[amount] == Integer.MAX_VALUE) return -1;return dp[amount];}
}遇到的困难
一开始其实递推公式想到了，但是初始化碰到了问题。最早是直接将dp[0]等于最大值，结果递推时没有限制dp[j-coins[i]]的大小，直接溢出了，后面就有点摸不着头脑了。还有dp[0]=0也很关键，因为按照定义目标值为0时硬币数就应该是0。
279.完全平方数
题目链接：279.完全平方数
代码随想录题解：279.完全平方数
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili
解题思路：
这题跟前一题其实是一样一样的，不同点在于coins这个数组由完全平方数[1*1,2*2,3*3.....]代替了。遍历时注意i*i和j都要小于n就可以。
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);}}}if (dp[n] == Integer.MAX_VALUE) return 0;else return dp[n];}
}看完代码随想录之后的想法
这题本质就是：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
这类求一共有多少组合的问题，先遍历物品或先遍历背包都不影响结果。
遇到的困难
一开始写的外层条件是i<=n，明显效率较低，因为背包内的物品是i*i，其值不能超过n，因此可以多加一点限制，提高效率。
今日收获
做了这么多题，感觉公式慢慢熟悉了，就是不知道碰到新的应用题能不能想到用背包做。
这篇关于代码随想录算法训练营第四十五天| 70. 爬楼梯 （进阶），322. 零钱兑换 ，279.完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
