Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
样例
Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9
public class Solution {
/**
* @param n a positive integer
* @return an integer
*/
public int numSquares(int n) {
// Write your code here
int[] maxSquares = new int[n + 1];
maxSquares[0] = 0;
maxSquares[1] = 1;
for(int i = 2;i <= n;i++){
maxSquares[i] = Integer.MAX_VALUE;
int sqrtNum = (int) Math.sqrt(i);
if(sqrtNum * sqrtNum == i){
maxSquares[i] = 1;
continue;
}
for(int j = 1;j <= sqrtNum;j++){
int minusNum = i - j * j;
if(maxSquares[i] > maxSquares[minusNum] + 1){
maxSquares[i] = maxSquares[minusNum] + 1;
}
}
}
return maxSquares[n];
}
}
