我有一個使用動態編程的問題的解決方案。我需要幫助將其從遞回解決方案轉變為迭代解決方案。
該函式接受一個數字并遵循三個規則：
- 它可能會將數字分成兩半
- 它可能會減去一個
- 它可能會添加一個
直到數字為 1。我的目標是找到執行此操作所需的最少步驟數。
這是我的解決方案：
def solution(n):
n = int(n)
memo = {}
return memoized_fuel_injection_perfection(n, memo)
def memoized_fuel_injection_perfection(n, memo):
if n == 1:
return 0
if n == 2:
return 1
if n in memo:
return memo[n]
if n % 2 == 0:
if n not in memo:
memo[n] = memoized_fuel_injection_perfection(n//2, memo) 1
return memo[n]
return min(memoized_fuel_injection_perfection(n-1, memo), memoized_fuel_injection_perfection(n 1, memo)) 1
但是，當我輸入長度超過 300 位的數字時，會出現遞回錯誤。我怎樣才能把它變成一個迭代的解決方案？任何幫助或指導表示贊賞。
這是我創建的一個迭代解決方案，但我得到的 MemoryError 輸入非常大。有什么方法可以優化存盤變數，這樣我就不必為每個數字計算它們？
def solution(n):
memo = {}
memo[0] = 0
memo[1] = 0
memo[2] = 1
n = int(n)
for i in range(3, n 1):
if i % 2 == 0:
memo[i] = memo[i//2] 1
else:
memo[i] = min(memo[i//2], memo[i//2 1]) 2
return memo[n]
uj5u.com熱心網友回復：
你說你在撰寫迭代解決方案時遇到的問題是使用memoized_fuel_injection_perfection(n 1, memo)，這使得確定計算結果的順序變得很棘手。關鍵是你不能無限地重復這個代碼路徑。如果可以，即使您的遞回解決方案也將無效。
在 1 或 -1 操作之后，您總是執行除以 2。我們可以將 1 或 -1 與除以 2 融合，產生一個不能增加數字的操作。迭代解決方案的核心將如下所示：
if n % 2 == 0:
table[n] = table[n//2] 1
else:
table[n] = min(table[n//2], table[n//2 1]) 2
你能從那里完成事情嗎？（您需要一種方法來避免計算每個小于 的正整數的結果n。）
uj5u.com熱心網友回復：
這是我的嘗試：
def solution(n):
def is_even(n): # helper function
return n % 2 == 0
possible_nodes = {1} # 1 is the destination
consider = [n] # stack: numbers to be considered
while consider: # as long as non-empty
x = consider.pop() # now think about where can we move from x
if x in possible_nodes: # if it is already handled before
continue
if is_even(x): # if even, we just halve it
consider.append(x//2)
else: # otherwise, -1 or 1
consider = [x-1, x 1]
possible_nodes.add(x) # mark x as 'considered'
steps = {1: 0} # dict to store min steps
for x in filter(is_even, sorted(possible_nodes)): # odds calculated only when needed
if x//2 not in steps: # if x//2 was not computed, x//2 must be odd
steps[x//2] = min(steps[x//2 - 1], steps[x//2 1]) 1
steps[x] = steps[x//2] 1
return steps[n] if is_even(n) or n == 1 else min(steps[n-1], steps[n 1]) 1
n = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003333000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003483983333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
print(solution(n)) # 2467
print(*(solution(i) for i in range(1, 21)))
# 0 1 2 2 3 3 4 3 4 4 5 4 5 5 5 4 5 5 6 5
代碼基本上由兩個步驟組成。在第一步中，它列舉所有可能的步驟n，根據規則x，
- 如果
x是偶數，我們只考慮x//2下一步；您的代碼中也采用了此策略； - 如果
x是奇數，我們將x-1和x 1作為下一步。
我這樣做是因為計算所有值的最小步驟n是浪費的。（實際上一開始我嘗試通過啟動類似的東西來做到這一點[None] * n，但似乎 python 無法處理這么長的串列。即使可以，我想這也會非常慢。）
下一步是計算最小步數，從最小的數字開始。我steps[x 1]通過“不急切地計算steps[x]奇數”來解決訪問問題x。我們只急切地計算steps[x]偶數x，而懶惰地計算奇數x。
理由如下；當x需要奇數時，它必須x是k//2 - 1或者k//2 1對于某些偶數 k，它必須大于x 1。由于x 1是偶數，因此step[x 1]必須已經通過for回圈的構造進行了計算。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/405881.html
標籤：