279. Perfect-Squares

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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.

Method One

class Solution {
    public int numSquares(int n) {
        //  dp[n] 是以 n 为结尾的最少的个数。
        //  确实是个经典的 dp 套路
        //  复杂度是 N \sqrt{N};
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i <= n; i++ ) {
            int min = Integer.MAX_VALUE;
            int j = 1;
            while( j*j <= i ) {
                min = Math.min( dp[ i - j*j ] + 1, min);
                j++;
            }
            dp[i] = min;
        }
        return dp[ n ];
    }
}
​