动态编程 - 斐波那契

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的表格。我知道它应该是一个列表，但我不确定它应该在函数内部还是外部，或者我应该用多少个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]

Answer 2

有一个简单的解决方案，对每个人都有效... ...

def fib(n):
    table = []
    table.append(0)
    table.append(1)
    for i in range(2, n+1):
        table.append(table[i-1] + table[i-2])
    return(table[n])