斐波那契数列有哪些实现方式？各有什么代价？

直接回答：四种主流实现：朴素递归 O(2^n)、记忆化递归或迭代动态规划 O(n)、滚动变量把空间降到 O(1)、矩阵快速幂 O(log n)。工程上用迭代滚动变量即可，矩阵快速幂是理论最优并常出现在追问中。

展开解析：朴素递归慢在子问题被指数级重复计算——fib(n−1) 和 fib(n−2) 的子树大量重叠，这正是「重叠子问题」的教科书案例，也是引入动态规划的最佳动机。记忆化是自顶向下加缓存，迭代 DP 是自底向上填表，二者复杂度相同但迭代没有递归栈开销。矩阵快速幂基于 [[1,1],[1,0]]^n 的第 (1,2) 元素即 fib(n)，把线性递推转化为幂运算再二分加速。追问方向：为什么朴素递归是 O(2^n) 而精确复杂度是 O(φ^n)（φ 为黄金比例）、尾递归改写后为什么 Python 里仍然慢（不做尾调用优化）、大 n 时的整数溢出与取模处理。

示例：

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a