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.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

对于一个正整数，找到一组完全平方数的和等于它，且完全平方数的数目最少。

使用一个数组，第i个元素代表对于正整数i的结果。
对于一个数i，我们一定可以把它拆为一个完全平方数和另一个数的和：i-jj与jj。而这里的i-j*j的结果我们已经有了。对比每一种拆法，看看那个拆法的结果最小：

res[i] = Math.min(res[i],res[i-j*j] + 1);

一直遍历到n，我们就得到了结果。

var numSquares = function(n) {
    if (n < 0)
        return 0;
    var res = [0];
    for (var i = 1;i <= n;i++) {
        for (var j = 1;j*j <= i;j++) {
            if (res[i]!==undefined) 
                res[i] = Math.min(res[i],res[i-j*j] + 1);
            else
                res[i] = res[i-j*j] + 1;
        }
    }
    return res.pop();
};