TA貢獻1884條經驗 獲得超4個贊
自上而下和自下而上的DP是解決相同問題的兩種不同方法?？紤]一種用于計算斐波那契數的記憶（自上而下）與動態（自底向上）編程解決方案。
fib_cache = {}
def memo_fib(n):
global fib_cache
if n == 0 or n == 1:
return 1
if n in fib_cache:
return fib_cache[n]
ret = memo_fib(n - 1) + memo_fib(n - 2)
fib_cache[n] = ret
return ret
def dp_fib(n):
partial_answers = [1, 1]
while len(partial_answers) <= n:
partial_answers.append(partial_answers[-1] + partial_answers[-2])
return partial_answers[n]
print memo_fib(5), dp_fib(5)
我個人覺得記憶很自然。您可以采用遞歸函數并通過機械過程將其記憶化（首先在緩存中查找答案，并在可能的情況下返回它，否則以遞歸方式對其進行計算，然后在返回之前將計算結果保存在緩存中以備將來使用），而自下而上動態編程要求您對計算解決方案的順序進行編碼，這樣在它依賴的較小問題之前就不會計算“大問題”。
舉報