代码随想录第45天 | 322. 零钱兑换、279. 完全平方数

322. 零钱兑换

动规五部曲分析如下：

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. 确定遍历顺序
   本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

所以本题并不强调集合是组合还是排列。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

/*** @param {number[]} coins* @param {number} amount* @return {number}*/
var coinChange = function (coins, amount) {const dp = Array(amount + 1).fill(Infinity)dp[0] = 0for (let i = 1; i <= amount; i++) {for (let j = 0; j < coins.length; j++) {if (i >= coins[j] && dp[i - coins[j]] !== Infinity) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)}}}return dp[amount] === Infinity ? -1 : dp[amount]
};

279. 完全平方数

1. 确定dp数组（dp table）以及下标的含义
   dp[j]：和为j的完全平方数的最少数量为dp[j]

2. 确定递推公式
   dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

3. dp数组如何初始化
   dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。

有同学问题，那0 * 0 也算是一种啊，为啥dp[0] 就是 0呢？

看题目描述，找到若干个完全平方数（比如 1, 4, 9, 16, …），题目描述中可没说要从0开始，dp[0]=0完全是为了递推公式。

非0下标的dp[j]应该是多少呢？

从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

4. 确定遍历顺序
   我们知道这是完全背包，

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

/*** @param {number} n* @return {number}*/
var numSquares = function (n) {let dp = new Array(n + 1).fill(Infinity)dp[0] = 0for (let i = 1; i <= n; i++) {for (let j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i - j * j] + 1, dp[i])}}return dp[n]
};