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