Мемоизация Фибоначчи в Python

Question

Я написал этот код для вычисления n-го числа Фибоначчи, и он работает (вычисляет правильное число), но не работает, потому что таблица не обновляется. Кто-нибудь знает почему?

# memoization
n = 12
table = np.ones(n+1)*-1
def fib3(n):
    if table[n]==-1:
        if n<=2:
            table[n] = 1
        else:
            table[n] = fib3(n-1)+fib3(n-2)
    #return table ##This was part of my original solution but I removed it because it wasn't working
fib3(12)

Это ошибка, которую я получаю из-за того, что таблица не обновляется (так как таблица [n] всегда = -1):

TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

Answer 1

Вы пропустили возврат значения функции fib3

import numpy as np

# memoization
n = 12
table = np.ones(n+1)*-1
def fib3(n):
    if table[n]==-1:
        if n<=2: 
            table[n] = 1
        else:
            table[n] = fib3(n-1)+fib3(n-2)
    return table[n]
fib3(12)

144

Answer 2

Вы явно ничего не возвращаете, поэтому ваша функция fib3 автоматически возвращает None. Таким образом, ваша строка table[n] = fib3(n-1) + fib3(n-2) оценивается как table[n] = None + None, и для None.

не определен оператор +.