使用动态规划求解斐波那契数时运行速度极慢，咨询与LeetCode缓存解法的性能差异原因

兄弟，你观察到列表和字典存取都是O(1)这点没错，但你忽略了一个关键问题：你的代码完全没有利用列表实现真正的缓存（记忆化）！

先拆解你的代码问题 #

你定义的result = [0]*(n+1)是在每个递归调用的fib函数内部创建的——也就是说，每次调用fib(n)、fib(n-1)、fib(n-2)时，都会生成一个全新的列表，之前计算过的结果根本不会被保留下来。举个例子：

• 计算fib(5)时，会调用fib(4)和fib(3)
• 计算fib(4)时，又会调用fib(3)和fib(2)
• 这里的两个fib(3)是完全独立的调用，各自都会重新计算fib(2)和fib(1)，没有任何复用

本质上你的代码就是普通的暴力递归，时间复杂度是O(2ⁿ)，n稍微大一点就会有巨量重复计算，自然超时。

再看参考解法的核心优势 #

参考解法里的cache = {0: 0, 1: 1}是类级别的属性——所有fib函数的递归调用都会共享这个字典。比如：

• 第一次计算fib(3)时，会把结果存入cache
• 当fib(4)再调用fib(3)时，直接从cache里取结果，不用再递归计算fib(2)和fib(1)

这才是真正的记忆化递归，时间复杂度降到了O(n)，所以速度快了几个数量级。

怎么修改你的代码让它变快？ #

如果你想用列表实现缓存，需要把列表变成共享的，比如改成类属性：

class Solution:
    def __init__(self):
        self.result = []  # 初始化共享缓存列表
    
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        # 确保缓存列表长度足够
        if len(self.result) <= n:
            self.result = [0]*(n+1)
            self.result[0] = 0
            self.result[1] = 1
        if self.result[n] != 0:
            return self.result[n]
        self.result[n] = self.fib(n-1) + self.fib(n-2)
        return self.result[n]

或者更简单的，直接用迭代式的动态规划（通常比递归记忆化更快）：

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        a, b = 0, 1
        for _ in range(2, n+1):
            a, b = b, a + b
        return b

内容的提问来源于stack exchange，提问作者superStar