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.
一刷
題解：
dynamic programming:
dp[n] = 1+min(dp[n-1], dp[n-4], ..., dp[n-root*root])
root = int(sort(n))
time complexity O(n^2), space complexity O(n)
public class Solution {
public int numSquares(int n) {
int root = new Double(Math.sqrt(n)).intValue();
int[] dp = new int[n+1];
for(int i=1;i<=root; i++){
dp[i*i] = 1;
}
for(int i=1; i<=n; i++){
int min = Integer.MAX_VALUE;
int i_root = new Double(Math.sqrt(i)).intValue();
for(int j=1; j<=i_root; j++){
min = Math.min(min, 1+dp[i-j*j]);
}
dp[i] = min;
}
return dp[n];
}
}
二刷
最開始想到的思路是砍艾，dp[n] = dp[i] + dp[n-i]忧便， 于是時(shí)間復(fù)雜度為O(n^2).這樣會(huì)出現(xiàn)嚴(yán)重超時(shí)。
如果只檢查完全平方數(shù)的dp片习，會(huì)讓時(shí)間復(fù)雜度降到O(n*sqrt(n)).
dp[n] = 1 + dp[n-root^2]
public class Solution {
public int numSquares(int n) {
if(n<=0) return 0;
int[] dp = new int[n+1];
int root = new Double(Math.sqrt(n)).intValue();
for(int i=1; i<=root; i++){
dp[i*i] = 1;
}
for(int i=2; i<=n; i++){
int min = Integer.MAX_VALUE;
int i_root = new Double(Math.sqrt(i)).intValue();
for(int j=1; j<=i_root; j++){
min = Math.min(1 + dp[i-j*j], min);
}
dp[i] = min;
}
return dp[n];
}
}
三刷
DP
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i=1; i*i<=n; i++){
dp[i*i] = 1;
}
for(int i=2; i<=n; i++){
int min = Integer.MAX_VALUE;
int root = (int)Math.sqrt(i);
for(int j=1; j<=root; j++){
min = Math.min(min, 1 + dp[i-j*j]);
}
dp[i] = min;
}
return dp[n];
}
}
