# 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.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
# Solution
Approach 1: DP (cache results in a class variable to speed things up).
# Code (Python)
Approach 1:
class Solution:
# have to use the class variable to speed things up :(
squares = [0, 1]
def numSquares(self, n: int) -> int:
# squares[v] -- least num of square numbers that sums up to v. Want squares[n]. Time: O(N * sqrt(N))
squares = self.squares # refer to the class variable with self.var
while len(squares) <= n:
v = len(squares)
i = int(v ** 0.5)
min_squares = float('inf')
while i >= 1:
min_squares = min(min_squares, 1 + squares[v - i * i])
if min_squares == 1: # early termination because num squares can't be less than 1
break
i -= 1
squares.append(min_squares)
return squares[n]
# OR with memoization
class Solution:
values = {0:0}
def numSquares(self, num: int) -> int:
if num < 0:
raise ValueError
values = self.values
if num in values:
return values[num]
int_square_root = math.floor(num ** 0.5)
if int_square_root ** 2 == num:
values[num] = 1
return 1
result = num
for i in range(int_square_root, 0, -1):
result = min(result, 1 + self.numSquares(num - i ** 2))
values[num] = result
return result
# Code (C++)
Approach 1:
class Solution {
private:
unordered_map<int,int> umap;
public:
int numSquares(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (umap.find(n) != umap.end())
return umap[n];
int min = n;
int i = sqrt(n);
for (; i > 0; --i)
{
int res = numSquares(n - i * i) + 1;
if (res < min)
min = res;
}
umap[n] = min;
return min;
}
};
class Solution {
public:
int numSquares(int n) {
vector<int> nums = vector<int>(n+1, n);
nums[0] = 0;
nums[1] = 1;
for (int i = 2; i <= n; ++i)
{
int s = sqrt(i);
if (s * s == i)
{
nums[i] = 1;
continue;
}
for (int j = 1; j <= s; ++j)
{
nums[i] = std::min(nums[i], nums[i - j * j] + 1);
}
}
return nums[n];
}
};