我正在嘗試解決找到最小數量的完美正方形（即 1、2、4、9 ..）的問題n
這是我的遞回自上而下的方法：
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)
我無法解釋為什么這段代碼沒有產生正確的結果。你能幫我找到錯誤嗎？
謝謝！
uj5u.com熱心網友回復：
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，并且每次移動到相鄰節點的成本為 1。在 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解決方案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/442122.html