LintCode Perfect Squares

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

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
28
29
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];
    }
}