我正试图解决求和为n的最小完美平方数(即1、2、4、9..(的问题
这是我的递归自上而下的方法：
import math
class Solution:
def numSquares(self, n: int) -> int:
dp = [math.inf] * (n + 1)
dp[0] = 0
dp[1] = 1
def solve(n: int):
if dp[n] != math.inf:
return dp[n]
for i in range(n, 0, -1):
if n - i * i >= 0:
sol = solve(n - i*i)
dp[i] = min(1 + sol, dp[i])
return dp[n]
solve(n)
print(dp)
Solution().numSquares(12)
我无法理解为什么这段代码没有产生正确的结果。你能帮我找到虫子吗？
谢谢！
class Solution:
def numSquares(self, n: int) -> int:
dp = [math.inf] * (n + 1)
dp[0] = 0
dp[1] = 1
def solve(n: int):
if dp[n] != math.inf:
return dp[n]
sol = math.inf
for i in range(n, 0, -1):
if n - i * i >= 0:
sol = min(sol, solve(n-i*i))
dp[n] = sol+1
return dp[n]
return solve(n)
以上是您的解决方案的更正版本，但它仍然太慢，因为您检查了每个数字，即使它们的平方明显大于n。以下是通过LC时间限制的优化版本：
class Solution:
def numSquares(self, n: int) -> int:
dp = [math.inf] * (n + 1)
dp[0] = 0
dp[1] = 1
def solve(n: int):
if dp[n] != math.inf:
return dp[n]
sol = math.inf
for i in range(1, n):
if n - i * i >= 0:
sol = min(sol, solve(n-i*i))
else:
break
dp[n] = sol+1
return dp[n]
return solve(n)
但仍有优化的空间。一点点：
class Solution:
def numSquares(self, n: int) -> int:
dp = [math.inf] * (n + 1)
dp[0] = 0
dp[1] = 1
def solve(n: int):
if dp[n] != math.inf:
return dp[n]
sol = math.inf
for i in range(1, math.floor(n**(1/2))+1):
sol = min(sol, solve(n-i*i))
dp[n] = sol+1
return dp[n]
return solve(n)
解决这一问题的另一种方法是使用BFS方法。将到达n的所有路径想象成一棵树，其中叶子的值为n，并且到相邻节点的每次移动都有一个代价。在BFS中，第一次命中是最好的命中，因为成本都是相等的：
class Solution:
def numSquares(self, n: int) -> int:
deq = collections.deque([n])
steps = 1
while deq:
n = len(deq)
for _ in range(n):
node = deq.popleft()
for i in range(1, floor(node**(1/2))+1):
num = i**2
if num == node:
return steps
deq.append(node - num)
steps += 1
正如Dmitry Bychenko所指出的，你可以使用拉格朗日定理来解决这个问题。这里有一个很好的写作和python解决方案。