Given an integer n, return the least number of perfect square numbers that sum ton.
A perfect square is an integer that is the square of an integer. For example, 1, 4, 9, 16, ...
Examples
I: n = 12
O: 3 (4 + 4 + 4)
I: n = 13
O: 2 (9 + 4)
Approach
A simple greedy approach won't work. A counter example is 12 where len(9 + 1 + 1 + 1) < len(4 + 4 + 4). The solution needs to be found recursively for each square root. We can see that some subproblems overlap here. Memoization can reduce the run time.
Brute Force Recursion
def numSquares(self, n: int) -> int:
min_count = self.search_squares_helper(n)
return min_count
def search_squares_helper(self, n: int) -> int:
# base case
if n == 0:
return 0
# recursive calls
float_root = math.sqrt(n)
biggest_root = int(math.floor(float_root))
min_count = 10001
for root in range(biggest_root, 0, -1):
count = 1 + self.search_squares_helper(n - root**2)
min_count = min(count, min_count)
return min_count
This is an exponential algo. TLE at n = 41.
Memoized Recursion
def numSquares(self, n: int) -> int:
memo: Dict[int, int] = {}
min_count = self.search_squares_helper(n, memo)
return min_count
def search_squares_helper(self, n: int, memo: Dict[int, int]) -> int:
# base case
if n == 0:
return 0
if n in memo:
return memo[n]
# recursive calls
float_root = math.sqrt(n)
biggest_root = int(math.floor(float_root))
min_count = 10001
for root in range(biggest_root, 0, -1):
count = 1 + self.search_squares_helper(n - root**2, memo)
min_count = min(count, min_count)
memo[n] = min_count
return min_count
This gets the run time down to the number of subproblems which are bounded by the input value. However, recursion has some overhead. OJ gives TLE when n = 8405.
DP
def numSquares(self, n: int) -> int:
dp: List[int] = [10001 for i in range(n + 1)]
# init
dp[0] = 0
dp[1] = 1
# topo order
for i in range(2, n + 1):
# recursive step
biggest_root = math.floor(math.sqrt(i))
for root in range(1, int(biggest_root) + 1):
dp[i] = min(dp[i], 1 + dp[i - root * root])
# final answer
return dp[n]
