dp_leetcode279

leetcode-279

思路方面我首先想到的是动态规划,如样例12=9+1+1+1 12=4+4+4

所以我们就可以找到状态转换的关键:

12-9=3 3-1=2 2-1=1 1-1=0 组合数为4

12-4=8 8-4=4 4-4=0 组合数为3

min(4,3) 答案取3

转态转换发生在目标数减去某一个平方数时 ,由大问题转换成小问题,12 转换3,3转换成2,2 转换成1

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numSquares(int n) {
int nums[]=new int[(int) (Math.floor(Math.sqrt(n))+1)];
for(int i=1;i<nums.length;i++){
nums[i]=(i)*(i); //初始化平方数组
}
int []dp =new int[n+1]; //1-n 的计数
for (int i = 1; i < n+1; i++) {
dp[i]=i; //初始化dp数组
}
for(int i=2;i<n+1;i++){
for(int j=nums.length-1;j>-1;--j){
if(i-nums[j]<0){
continue;
}else{
dp[i]=Math.min(dp[i-nums[j]]+1,dp[i]);
//状态转换
}
}
}
return dp[n];
}

此算法超过了49.89%的算法,但是据说是一个数学问题:

四平方和定理:任意一个正整数均可表示为4个以内(1,2,3,4….)整数的平方和

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int numSquares(int n) {
//四平方和定理:任意一个正整数均可表示为4个以内(1,2,3,4)整数的平方和
while (n % 4 == 0){
n /= 4;
}
if (n %8 == 7){
return 4;
}
for (int a = 0; a * a <= n; a++){
int b = (int)Math.sqrt(n - a * a);
if (a * a + b * b == n){
if (a == 0 || b == 0){
return 1;
} else {
return 2;
}
}
}
return 3;
}