在 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]

但我在 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，您引用的是相对于列表末尾的列表元素。

implementing bottom up fibonacci in python