代码随想录算法训练营第四十五天| 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];
    }
}