279. 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.

Example 1:

Input:
n
 = 
12
Output:
 3 

Explanation: 
12 = 4 + 4 + 4.

Example 2:

Input:
n
 = 
13
Output:
 2

Explanation: 
13 = 4 + 9.

Solution

(1) Java

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

(2) Python

(3) Scala