動態規劃 - 斐波那契

Question

所以基本上，我是一個學習程序員，本週我介紹了動態規劃。我們的任務是使用動態規劃來找到斐波那契數列。這個僞代碼是提供這顯然是一個函數：

init table to 0s 
if n ≤ 1 
    return n 
else 
    if table[n-1] = 0 
     table[n-1] = dpFib(n-1) 
    if table[n-2] = 0 
     table[n-2] = dpFib(n-2) 
    table[n] = table[n-1] + table[n-2] 
return table[n] 

多數，這是簡單的切換到代碼，但我不知道如何初始化0的表。我知道它應該是一個列表，但我不確定它應該在函數內部還是外部，或者我應該初始化多少個零。這是我寫的，沒有什麼複雜的：

def dynamicFibo(n): 
    # initialise table of 0s 
    #base case 
    if n <= 1: 
     return n 
    #recursive case 
    else: 
     if table[n-1] == 0: 
      table[n-1] = dynamicFibo(n-1) 

     if table[n-2] == 0: 
      table[n-2] = dynamicFibo(n-2) 

     table[n] = table[n-2] + table[n-2] 
    return table[n] 

我會感激，如果有人能告訴我的方式去與此。另外，總的來說，我很難理解動態規劃的基礎，所以如果有什麼好的資源可以建議我會很高興，或者即使你能給出一個好的解釋。

Answer 1

就可以初始化你table有：

table = [0 for _ in range(n+1)] 

，因爲你要在你的表中至少n+1項目以允許訪問table[n]（記住，列表是零索引，因此nth項目與訪問(n-1)）

但是，您會希望確保每次都不會創建新列表，因爲這會破壞動態編程的目的。因此，您可以將table稱爲「不可見」參數，即帶有每次遞歸調用時使用的默認參數的參數。那麼你的功能應該是這樣的：

>>> def dynamicFibo(n,table = []): 
    while len(table) < n+1: table.append(0) #this does the same thing except it doesn't change the reference to `table` 
    #base case 
    if n <= 1: 
     return n 
    #recursive case 
    else: 
     if table[n-1] == 0: 
      table[n-1] = dynamicFibo(n-1) 

     if table[n-2] == 0: 
      table[n-2] = dynamicFibo(n-2) 

     table[n] = table[n-2] + table[n-1] 
    return table[n] 
>>> dynamicFibo(12) 
144 
>>> dynamicFibo(300) 
222232244629420445529739893461909967206666939096499764990979600 

reference

，你可以看到，我用了while循環，而不是一個列表理解。除了我們不能更改table的引用，否則遞歸調用每次都會創建一個新表，除非您將它作爲參數傳遞，否則這基本上是相同的。如果您使用不斷增加的號碼多次呼叫dynamicFibo，則還可以根據需要展開表格，但保留所有舊號碼。

>>> dynamicFibo(12) 
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 1, 1, 2, 3, 5, 0, 0, 0, 0, 0, 0, 0] 
[0, 1, 1, 2, 3, 5, 8, 0, 0, 0, 0, 0, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 0, 0, 0, 0, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 0, 0, 0, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 0, 0, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144] 
144 
>>> dynamicFibo(14) 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 0] 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377] 
377 

我加入了print(table)權利之前return table[n]

：這顯然是在函數添加 print(table)線看