Trace
6.11 每日一题
传送门：https://leetcode-cn.com/problems/perfect-squares/
Problem
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例
1
2
3
| 输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
|
1
2
3
| 输入：n = 13
输出：2
解释：13 = 4 + 9
|
数据范围
lc题解
$f[i]$表示至少需要多少个完全平方数来组成$i$，假设$j$是组成$i$的其中一个完全平方数，则$f[i]=f[i-j^2]+1$，形成递推关系，每次只需要从完全平方数中找$f[i-j^2]$较小的即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numSquares(int n) {
int f[10001];
f[0]=0;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=sqrt(i);j++){
f[i]=min(f[i],f[i-j*j]+1);
}
}
return f[n];
}
};
|
方法二
将题意转化为：用给定数组中的数来组成$n$，每个数可以取无数次，求最少需要多少个数。
裸的完全背包，需要注意的是求$min$而不是$max$，用给定的完全平方数恰好组成$n$，而不是不超过$n$，（$n$就相当于完全背包中的体积）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int f[101][10001];
int numSquares(int n) {
for(int i=0;i*i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j]=0x3f3f3f3f;
}
}
f[0][0]=0;
for(int i=1;i*i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j]=f[i-1][j];
if(j>=i*i){
f[i][j]=min(f[i][j],f[i][j-i*i]+1);
}
}
}
return f[(int)sqrt(n)][n];
}
};
|
优化空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int f[10001];
int numSquares(int n) {
for(int i=0;i<=n;i++){
f[i]=0x3f3f3f3f;
}
f[0]=0;
for(int i=1;i*i<=n;i++){
for(int j=i*i;j<=n;j++){
f[j]=min(f[j],f[j-i*i]+1);
}
}
return f[n];
}
};
|
时间复杂度：$O(n*sqrt(n))$，空间复杂度$O(n)$。
