动态规划
解题思路
确定 dp 数组以及下标的含义：dp[j]：和为 j 的完全平方数的最少数量为 dp[j]
确定递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j])
如何初始化 dp 数组：
- dp[0] 表示和为 0 的完全平方数的最小数量，那么 dp[0] 一定是 0
- 每次 dp[j] 都要选最小的，则非 0 下标的 dp[j] 一定要初始为最大值，这样 dp[j] 在递推的时候才不会被初始值覆盖；
确定遍历顺序：
- 0-1 背包 参考 上一行 的值，使用一维数组压缩空间的时候，倒序 填表；
- 完全背包 参考 当前行 的值，使用一维数组压缩空间的时候，正序 填表；
举例推导 dp 数组：以 n = 8 为例：
总和 j = 0 总和 j = 1 总和 j = 2 总和 j = 3 总和 j = 4 总和 j = 5 总和 j = 6 总和 j = 7 总和 j = 8 初始化 dp 0 Infinity Infinity Infinity Infinity Infinity Infinity Infinity Infinity i = 1，平方为 1 0 1 2 3 4 5 6 7 8 i = 2，平方为 4 0 1 2 3 1 2 3 4 2
实现代码
var numSquares = function (n) {
// 1. 声明 dp
let dp = Array(n + 1).fill(Infinity);
// 2. 初始化 dp
dp[0] = 0;
for (let i = 1; i ** 2 <= n; i++) { // 物品
let val = i ** 2;
for (let j = val; j <= n; j++) { // 背包
dp[j] = Math.min(dp[j - val] + 1, dp[j]);
}
}
return dp[n];
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 322. 零钱兑换
上一篇
评论
