реализация снизу вверх фибоначчи в python

Question

Я пытаюсь реализовать нижнюю версию фибоначчи, которая работает в O (n), но продолжает получать ошибки индекса списка, и я не знаю, почему. Это мой код:

def fibbu(n): 
    fib = [1,1] 
    for i in range(2, n): 
     fib[i] = fib[i-2] + fib[i-1] 
    return fib[n] 

Но я получаю indexerror на линии внутри цикла for. Я слишком долго занимался чем-то таким простым, может ли кто-нибудь указать, где я ошибаюсь?

Answer 1

Это будет работать:

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

У вас был список из двух элементов, и вы пытаетесь изменить третий элемент, следовательно, исключение. В приведенном выше коде мы добавляем новые элементы в конец списка. Индекс -1 означает последний элемент, -2 второй последний. Обратите внимание, что вам больше не нужно i, вы ссылаетесь на элементы списка относительно его конца.