279. Perfect Squares
這一個題目是一個非常彈性的題目，題目的問題非常簡單，找到最少個完全平方數其總和為題目給定的 n 。
首先第一個要先想到的是，我們要找的完全平方數，一定是比這個數還來的小，因此我們就可以先計算出可以利用的完全平方數的範圍為何。
perfect_nums = [i * i for i in range(1, int(n**0.5)+1)]
此時我們就可以建構出這個問題的樹是如何，以 n = 12 為例子，perfect_nums = [1, 4, 9] ，這個樹的樣子就會長得像這樣。
[12]
[11, 8, 9]
[[10, 7, 2], [7, 4], [2]]
...
class Solution:
def numSquares(self, n: int) -> int:
perfect_nums = [i ** 2 for i in range(1, int(n**0.5)+1)]
@lru_cache(None)
def dp(n):
if n == 0:
return 0
return 1 + min([dp(n-num) for num in perfect_nums if num <= n])
return dp(n)
class Solution:
def numSquares(self, n: int) -> int:
perfect_nums = [i * i for i in range(1, int(n**0.5)+1)]
queue = deque([n])
level = 0
while queue:
level += 1
size = len(queue)
for i in range(size):
node = queue.popleft()
for child in perfect_nums:
if child == node:
return level
elif child > node:
break
else:
queue.append(node - child)