I am trying to implement the bottom up version of fibonacci that operates in O(n) time but keep getting list assignment index errors and I have no clue why. This is my code:
def fibbu(n):
fib = [1,1]
for i in range(2, n):
fib[i] = fib[i-2] + fib[i-1]
return fib[n]
But I am getting an indexerror on the line inside of the for loop. I've spent far too long on something so simple, can anyone point out where I'm going wrong?
This will work:
def fibbu(n):
fib = [1,1]
for _ in range(2, n):
fib.append(fib[-2] + fib[-1])
return fib[-1]
You had a list of two elements and you were trying to modify the third element, hence the exception. In the code above, we're appending new elements to the end of the list. Index -1 means the last element, -2 the second last. Note that you actually don't need i anymore, you're referencing elements of the list relative to its end.
