Динамическое программирование - Fibonacci

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] 

Большинство это было просто, чтобы изменить код, но я не уверен, как инициализировать таблицу 0s. Я знаю, что это должен быть список, но я не уверен, должен ли он находиться внутри функции или снаружи или сколько нулей мне нужно инициализировать. Это то, что я не писал, ничего сложного:

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

, как вы можете видеть, я использовал время цикла вместо списка понимания. Это по сути то же самое, за исключением того, что мы не можем изменить ссылку 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]