动态编程-斐波那契 [英] Dynamic Programming - Fibonacci
问题描述
因此，基本上，我是一名学习型程序员，本周向我介绍了动态编程.我们的任务是使用动态编程找到斐波那契数列.提供了此伪代码，该伪代码显然将存在于函数中:
So basically, I am a learning programmer and this week I was introduced to dynamic programming. Our task was to find the Fibonacci sequence using dynamic programming. This pseudo code was supplied which would obviously be in a function:
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]
其中大部分很容易更改为代码，但是我不确定如何初始化0s表.我知道它应该是一个列表，但是我不确定它应该在函数内部还是外部，或者应该使用多少个零初始化.这就是我写的，没什么复杂的:
The majority of this was simple to change to code but I'm not sure how to initialise the table of 0s. I know it should be a list but I'm not sure if it should be inside the function or outside or how many zeros I should initialise it with. This is what I wrote, nothing complicated:
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]
如果有人能告诉我解决方法，我将非常感激.另外，总的来说，我很难理解动态编程的基础，因此，如果有什么好的资源，您可能会建议我感到高兴，或者即使您能提供一个很好的解释.
I would be thankful if someone could show me the way to go with this. Also, in general I struggle to understand the basis of dynamic programming so if there are any good resources you could suggest I would be delighted, or even if you could give a good explanation.
推荐答案
您可以使用以下方法初始化表:
you can initialize your table with:
table = [0 for _ in range(n+1)]
因为您要在表中至少包含 n + 1 个项目以允许访问 table [n] (请记住列表的索引为零，所以 nth 项通过(n-1))
since you want to have at least n+1 items in your table to allow to access table[n] (remember that lists are zero-indexed so the nth item is accessed with (n-1))
但是，您将要确保每次都不会创建新列表，因为这样做会破坏动态编程的目的.因此，您可以使用 table 作为我所谓的不可见"参数，即，在每个递归调用中都使用具有默认参数的参数.您的函数将如下所示:
However, you would want to ensure that you are not creating new lists every time since that would defeat the purpose of dynamic programming. So you can have table as what I call an "invisible" parameter, ie a parameter with a default parameter that is used at every recursive call. Your function would then look like this:
>>> 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)行可以清楚地看到这一点:
as you can see, I used a while loop instead of a list comprehension. This is essentially the same thing except we cannot be changing the reference of table or else the recursive calls will create a new table each time unless you pass it in as a paramater. This also allows the table to expand as necessary if you call dynamicFibo more than once with increasing numbers, but maintain all the old numbers. This is clearly seen by adding a print(table) line in the function:
>>> 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
我在返回表[n]
这篇关于动态编程-斐波那契的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
