动态规划 - 斐波那契

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)线看