Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
Constraints:
1 <= n <= 104
Idea: (Dynamic Programing)
- Time complexity: O(n * sqrt(n))
- Space complexity: O(n)
dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 =
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 =
dp[0] + 5 = 5
};
so dp[5] = 2
Solution:
/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
// Important: n + 1 length because we use dp[0]
let dp = new Array(n + 1).fill(Number.MAX_VALUE);
dp[0] = 0;
for (let i = 1; i <= n; i++)
for(let j = 1; j * j <= i; j++)
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
return dp[n];
};