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.

對(duì)于一個(gè)正整數(shù)，找到一組完全平方數(shù)的和等于它，且完全平方數(shù)的數(shù)目最少。

使用一個(gè)數(shù)組，第i個(gè)元素代表對(duì)于正整數(shù)i的結(jié)果。
對(duì)于一個(gè)數(shù)i，我們一定可以把它拆為一個(gè)完全平方數(shù)和另一個(gè)數(shù)的和：i-jj與jj。而這里的i-j*j的結(jié)果我們已經(jīng)有了。對(duì)比每一種拆法，看看那個(gè)拆法的結(jié)果最?。?/p>

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

一直遍歷到n，我們就得到了結(jié)果。

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();
};