279 Perfect Squares

Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.

Example 1:

Input:
n
 = 
12
Output:
 3 

Explanation: 
12 = 4 + 4 + 4.

Example 2:

Input:
n
 = 
13
Output:
 2

Explanation: 
13 = 4 + 9.

class Solution {
    public int numSquares(int n) {
        if(n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
}