动态规划 - 斐波那契

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

参考

如您所见，我使用了 while 循环而不是列表理解。这本质上是一样的，除了我们不能改变 的引用，table否则递归调用每次都会创建一个新表，除非你将它作为参数传入。如果您dynamicFibo多次调用增加的号码，这也允许表格根据需要扩展，但保留所有旧号码。通过print(table)在函数中添加一行可以清楚地看到这一点：

>>> 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]