友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
279. 完全平方数
给你一个整数 n，返回 和为 n 的完全平方数的最少数量。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
提示：
-
1 <= n <= 104
思路分析
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Runtime: 45 ms, faster than 31.57% of Java online submissions for Perfect Squares.
*
* Memory Usage: 41.2 MB, less than 13.89% of Java online submissions for Perfect Squares.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-24 11:34
*/
public int numSquares(int n) {
if (n <= 0) {
return 0;
}
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = i; // 最坏的情况就是每次+1，也就是分解为 i 个 1*1
for (int j = 1; i - j * j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-19 22:06:00
*/
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
// 外层遍历物品
for (int i = 1; i * i <= n; i++) {
// 内层遍历体积
for (int j = i * i; j <= n; j++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}