1. 问题描述 【LeetCode|LeetCode刷题笔记（279.完全平方数）】给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
2. 解题思路 完全平方数 ===> 物品
正整数 n ===> 背包
题目转化为 ==> 用多少 物品 装满 背包
① 确定 dp 数组
dp[i] 表示和为 i 的完全平方数的最少数量
示例：dp[12] = 3
解释：dp[12]表示和为12（12 = 1 * 1 + 2 * 2 + 3 * 3）包含了1，2，3一共三个完全平方数
② 确定递推公式
由 dp[i - j * j] 可推出 dp[i]
dp[i - j * j] + 1 可以凑成dp[i]
此时要选择最小的 dp[i]，所以递推公式为
dp[i] = min(dp[i - j * j] + 1, dp[i])
③ dp数组初始化
dp[0]表示和为 0 的完全平方数的最少数量，则dp[0] = 0;
从递推公式 dp[i] = min(dp[i - j * j] + 1, dp[i]);
中可以看出每次dp[j]都要选最小的，所以非0下标的dp[i]一定要初始为最大值，这样dp[i]在递推的时候才不会被初始值覆盖。
④ 确定遍历顺序
本题为完全背包
如果求组合数就是外层for循环遍历物品，内层for循环遍历背包;
如果求排列数就是外层for循环遍历背包，内层for循环遍历物品。
⑤ 推导dp数组
dp[0] = 0
dp[1] = min(dp[0] + 1) = 1
dp[2] = min(dp[1] + 1) = 2
dp[3] = min(dp[2] + 1) = 3
dp[4] = min(dp[3] + 1, dp[0] + 1) = 1
dp[5] = min(dp[4] + 1, dp[1] + 1) = 2
3. 代码实现
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;
}
// 当和为 0 时，组合的个数为 0
dp[0] = 0;
// 遍历背包
for (int i = 1;
i <= n;
i++) {
// 遍历物品
for (int j = 1;
j * j <= i;
j++) {
dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
}
}
return dp[n];
}
}
推荐阅读
- mybatis|mybatis-config.xml 以及遇到的问题
- #|MyBatis-第一个MyBatis程序
- 分治|【模拟赛|ZROI】01串（容斥，分治FFT）
- Java|初学Mybatis-第一个Mybatis程序及踩坑解决
- 机器学习|CVPR 2022 接收结果出炉！录用 2067 篇，接收数量上升24%（附最新论文速递）
- 如何在 github 上找到优质代码
- 算法|一举打败16个同类模型，视频超分比赛冠军算法入选CVPR 2022，来自商汤&南洋理工大学...
- 蓝桥杯|2021第十二届蓝桥杯大赛软件赛省赛C/C++ 大学B组试题B杨辉三角形
- 2021第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组