TA貢獻(xiàn)1884條經(jīng)驗(yàn) 獲得超4個(gè)贊
自上而下和自下而上的DP是解決相同問題的兩種不同方法?？紤]一種用于計(jì)算斐波那契數(shù)的記憶（自上而下）與動態(tài)（自底向上）編程解決方案。
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)
我個(gè)人覺得記憶很自然。您可以采用遞歸函數(shù)并通過機(jī)械過程將其記憶化（首先在緩存中查找答案，并在可能的情況下返回它，否則以遞歸方式對其進(jìn)行計(jì)算，然后在返回之前將計(jì)算結(jié)果保存在緩存中以備將來使用），而自下而上動態(tài)編程要求您對計(jì)算解決方案的順序進(jìn)行編碼，這樣在它依賴的較小問題之前就不會計(jì)算“大問題”。
舉報(bào)