279. Perfect Squares

Description

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.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution

DP, time O(n * sqrt(n)), space O(n)

本来以为会有什么dark magic，随便写了个DP就过啦竟然。

class Solution {
    public int numSquares(int n) {
        int[] count = new int[n + 1];
        count[0] = 0;
        
        for (int i = 1; i <= n; ++i) {
            count[i] = i;   // made up with 1
            
            for (int j = (int) Math.sqrt(i); j > 0; --j) {
                count[i] = Math.min(count[i], 1 + count[i - j * j]);
            }
        }
        
        return count[n];
    }
}