279. Perfect Squares

[Tcdian]

279. Perfect Squares

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

Example 1

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const dp = Array.from(new Array(n + 1), (val, index) => index);
    for (let i = 1; i <= n; i++) {
        let j = Math.floor(Math.sqrt(i));
        while (j > 0) {
            dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            j--;
        }
    }
    return dp[n];
};

• TypeScript Solution

function numSquares(n: number): number {
    const dp: number[] = Array.from(new Array(n + 1), (val, index) => index);
    for (let i = 1; i <= n; i++) {
        let j = Math.floor(Math.sqrt(i));
        while (j > 0) {
            dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            j--;
        }
    }
    return dp[n];
};