代码随想录算法训练营第四十五天 | LeetCode 70. 爬楼梯、322. 零钱兑换、279. 完全平方数
1. LeetCode 70. 爬楼梯
1.1 思路
- 我们做动态规划基础时做过这题，现在可以当做完全背包来做。楼梯阶数 n 即背包容量，一次跳 1 阶或者 2 阶即物品，这两个阶数就是物品。问跳到 n 有多少种方法即装满背包有多少种方法
- 确定 dp 数组及其下标的含义：dp[i] 爬到有 i 个台阶的楼顶有 dp[i] 种方法
- 递推公式：在494. 目标和、518. 零钱兑换 II、377. 组合总和 Ⅳ中讲过求装满背包有多少种方法，递推公式一般是 dp[i]+=dp[i-nums[j]]。本题 dp[i] 有 dp[i-1]、dp[i-2]等等即 dp[i-j]。因此递推公式就是 dp[i]+=dp[i-j]
- dp 数组的初始化：根据递推公式 dp[0] 只能 为 1 不能为 0，为 0 后面就无法递推
- 遍历顺序：本题求的是排列问题，因为 用 1 步再用 2 步和用 2 步再用 1 步是两种方法，因此要先背包后物品，这样才是求排列数。for（int i=1；i<=n；i++）for（int j=1；j<=2；j++）这里 j<=2 是因为只有两种物品。然后只有 i>=j 时才 dp[i]+=dp[i-j] 因为只有当前背包容量大于等于物品重量才记录当前方法
1.2 代码
class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; int m = 2; //有兩個物品：itme1重量爲一，item2重量爲二 dp[0] = 1; for (int i = 1; i <= n; i++) { // 遍历背包 for (int j = 1; j <= m; j++) { //遍历物品 if (i >= j) //當前的背包容量 大於 物品重量的時候，我們才需要記錄當前的這個裝得方法（方法數+） dp[i] += dp[i - j]; } } return dp[n]; } }
2. LeetCode 322. 零钱兑换
2.1 思路
- 在518. 零钱兑换 II我们要求的是有多少种方法能兑换成 amount，本题中是要求用最少的硬币数兑换成 amount，本题物品就是硬币，背包容量就是 amount
- dp 数组及其下标的含义：dp[j]： 凑足金额为 j 所需的硬币最少个数为 dp[j]
- 递推公式：凑足金额为 j-coins[i] 的最少个数为 dp[j-coins[i]]，只需要再加一个硬币 coins[i] 即dp[j-coins[i]]+1 就是 dp[j]。所以 d[j] 要取所有 dp[j-coins[i]]+1 中最少的即 dp[j]=Math.min（dp[j-coins[i]]+1，dp[j]）
- dp 数组的初始化：dp[0]=0 因为总金额为 0 所需硬币肯定为 0，其余下标，由于递推公式是求最小值，因此其他下标的值应为 Interger.MAX_VALUE，否则就有可能把递推公式得到的值给覆盖掉
- 遍历顺序：本题先物品后背包或者先背包后物品都可以，因为是求硬币最少数，硬币有无顺序均可，不影响最少个数，所以本题不强调组合还是排列。求组合数就先物品再背包，求排列数就是先背包再物品。我们就先物品再背包 for（int i=0；i<coins.length；i++）for（int j=coins[i]；j<=amonut；j++）if（dp[j-coins[i]]!=Interger.MAX_VALUE）就dp[j]=Math.min（dp[j-coins[i]]+1，dp[j]）
- 打印 dp 数组：用于 debug
2.2 代码
class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp = new int[amount + 1]; //初始化dp数组为最大值 for (int j = 0; j < dp.length; j++) { dp[j] = max; } //当金额为0时需要的硬币数目为0 dp[0] = 0; for (int i = 0; i < coins.length; i++) { //正序遍历：完全背包每个硬币可以选择多次 for (int j = coins[i]; j <= amount; j++) { //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要 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. LeetCode 279. 完全平方数
3.1 思路
- 本题要求用最少的完全平方数凑成 n，物品就是这些完全平方数，容量就是 n，思路跟518. 零钱兑换 II是一样的
- dp 数组及其下标的含义：dp[j]： 和为 j 所需的完全平方数最少个数为 dp[j]
- 递推公式：dp[j] 可以由 dp[j-ii] 推出，dp[j-ii]+1 便可以凑成 dp[j}，dp[j]=Math.min(dp[j-ii]+1,dp[j])。这里写成 ii 就是保证这是完全平方数
- dp 数组的初始化：dp[0]=0 因为和为 0 所需最少完全平方数肯定为 0，本题没有 0*0 的完全平方数，因此其他下标的值应为 Interger.MAX_VALUE
- 遍历顺序：本题先物品后背包或者先背包后物品都可以，因为是求完全平方数的最少数，有无顺序不影响最少个数，因此不强调组合还是排列。for(int i=1;ii<=n;i++)for(int j=ii;j<=n;j++)ii 要小于等于 n，如果比 n 都大了就没有意义了，然后 j 就是从 ii 这个物品开始，为了就是 dp[j-i*i] 不要出现负数
- 打印 dp 数组：主要用于 debug
3.2 代码
class Solution { // 版本一，先遍历物品, 再遍历背包 public int numSquares(int n) { int max = Integer.MAX_VALUE; int[] dp = new int[n + 1]; //初始化 for (int j = 0; j <= n; j++) { dp[j] = max; } //如果不想要寫for-loop填充數組的話，也可以用JAVA內建的Arrays.fill()函數。 //Arrays.fill(dp, Integer.MAX_VALUE); //当和为0时，组合的个数为0 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); //} //不需要這個if statement，因爲在完全平方數這一題不會有"湊不成"的狀況發生（ 一定可以用"1"來組成任何一個n），故comment掉這個if statement。 } } return dp[n]; } }
