斐波那契：动态规划入门示例

斐波那契数列的递推公式如下：

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}.

直接递归会反复计算相同的子问题，时间复杂度呈指数级增长。记忆化（Memoization）让 $n+1$ 个不同状态各计算一次，避免重复计算；若采用自底向上（Bottom-up）的方式，则能显式地体现状态间的依赖顺序。

记忆化后的 Fibonacci 递归树：缓存读写代替重复子树的计算。 — 绿色向下箭头把刚算出的值写入缓存，红色向上箭头直接读取已有结果。右侧再次需要 F5 时，缓存里已有答案，灰色子树就不必展开。图中用记忆化递归求 F7 = 13；下方循环则进一步按顺序计算，只保留下一次加法需要的两个值。
Jeff Erickson，《Algorithms》图 3.2（第 101 页）；由 PDF 裁取。 · CC BY 4.0

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

状态压缩

若使用完整数组存储，需保留从 $F_0$ 到 $F_n$ 的所有值。但观察转移方程可知，计算当前值仅依赖前两个值，因此只需维护两个变量即可：

时间复杂度： $O(n)$ 次算术运算；
空间复杂度： $O(1)$ 个整数变量；
注意：整数本身的位宽随 $n$ 增长，因此对于极大下标，单次加法的位复杂度并非常数。

示例启示

斐波那契数列是识别“重叠子问题”和进行“安全内存压缩”的经典入门案例，但它并非具有代表性的复杂优化问题。利用额外的代数结构（如快速倍增法或矩阵快速幂），可以在 $O(\log n)$ 的递推深度内计算出 $F_n$ 。

在 Python 记忆化示例中，应避免使用可变对象（如字典）作为默认参数。缓存的所有权归属与生命周期应当显式管理，以避免潜在的副作用。

跟踪执行与整数开销

第 k 次迭代前，(previous, current) 等于 (F_k, F_(k+1))。同时赋值保持这个不变量，完成 n 次后 previous 就是答案。n=5 时，数对依次为 (0,1)、(1,1)、(1,2)、(2,3)、(3,5)、(5,8)，返回 5。n=0 时不进入循环，返回 0；负数会被拒绝。输入必须是整数。

两个变量意味着整数个数恒定，不意味着任意 n 下固定宽度机器字的个数恒定。斐波那契数需要 Θ(n) 位。若整数加法时间与位数成正比，整个循环需 O(n²) 次位操作、O(n) 位辅助空间。

assert fibonacci(0) == 0
assert fibonacci(5) == 5

在 USF Fibonacci 演示中用 6 这样的小下标，对比递归、记忆化和表格三种模式。分别数“不同子问题下标”和“总调用次数”，先看清缓存省下了什么，再理解双变量循环为什么还能省掉整张表。演示的初值是 1、1，与本文的 0、1 相比数列平移了一位；这里重点比较子问题复用过程。

参考来源

MIT OpenCourseWare: Dynamic Programming I

探索关联

被引用 (1)

动态规划

同主题的其他笔记 (36)

打开关联网络

状态压缩​

示例启示​

跟踪执行与整数开销​

参考来源​