LC 0279 [M] Perfect Squares - ALawliet/algorithms GitHub Wiki
just like Coin Change
class Solution:
def numSquares(self, n: int) -> int:
cache = [n] * (n + 1)
cache[0] = 0
for i in range(1, n + 1):
for s in range(1, i + 1):
square = s * s
if i - square < 0:
break
if 1 + cache[i - square] < cache[i]:
cache[i] = 1 + cache[i - square]
return cache[n]
class Solution:
def numSquares(self, n: int) -> int:
dp = [n] * (n + 1)
dp[0] = 0
squares = [x**2 for x in range(1, n) if x**2 <= n] # passes TLE
for target in range(1, n + 1):
for square in squares:
if target - square < 0:
break
dp[target] = min(dp[target], 1+dp[target-square])
return dp[n]