题目要求
1
2
3
| Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
|
判断一个数字最少由几个平方数的和构成。比如12=9+1+1+1=4+4+4，那么最少的数量为3。
思路一：暴力递归
要想知道什么样的组合最好，暴力比较所有的结果就好啦。当然，效率奇差。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int numSquares(int n) {
if(n==0) return 0;
if(n==1) return 1;
int sqrt = (int) Math.floor(Math.sqrt(n));
int count = Integer.MAX_VALUE;
while(sqrt>0){
int tmpCount = 0;
int copy = n;
do{
copy -= sqrt * sqrt;
tmpCount++;
}while(copy > sqrt * sqrt);
count = Math.min(count, tmpCount+numSquares(copy));
sqrt--;
}
return count;
}
|
思路二：动态规划
我们可以用另一种思路来拆解n：
比如：
numSquares(1) = 1;
numSquares(2) = numSquares(1)+1
numSquares(3) = numSquares(3-1*1) + 1
numSquares(4) = 1
numSquares(5) = min(numSquares(5-1*1)+1, numSquares(5-2*2)+1)
numSquares(10) = min(numSquares(10-1*1)+1, numSquares(10-2*2)+1, numSquares(10-3*3)+1)
这样我们就可以省去许多重复的计算。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int numSquares_dp(int n){
if(n<=1) return n;
int[] min = new int[n+1];
min[1] = 1;
for(int i = 2 ; i<=n ; i++){
int sqrt = (int)Math.floor(Math.sqrt(i));
int tempMin = Integer.MAX_VALUE;
while(sqrt-->0){
tempMin = Math.min(tempMin, min[n-sqrt*sqrt]);
sqrt--;
}
min[i] = tempMin;
}
return min[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
| public int numSquares_math(int n){
if(isSquare(n)) return 1;
while ((n & 3) == 0)
{
n >>= 2;
}
if ((n & 7) == 7)
{
return 4;
}
int sqrt_n = (int)(Math.sqrt(n));
for(int i = 1; i <= sqrt_n; i++)
{
if (isSquare(n - i*i))
{
return 2;
}
}
return 3;
}
|