I'm trying to solve this problem
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
I've come up with a solution that works correctly but times out on large inputs:
from collections import defaultdict
class Solution:
def numSquares(self, n: int) -> int:
coins = []
for i in range(1, n+1):
if i**2>n:
break
coins.append(i**2)
min_coins_to_make = defaultdict(lambda :float("inf"))
min_coins_to_make[0] = 0
for coin in coins:
if coin > n:
break
for target in range(coin, n+1):
min_coins_to_make[target] = min(min_coins_to_make[target], 1+min_coins_to_make[target-coin])
if min_coins_to_make[target] == float("inf"):
return 0
return min_coins_to_make[target]
How do I optimize it in terms of time and space complexity?