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

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

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

直接递归会反复计算相同的子问题，时间复杂度呈指数级增长。引入记忆化（Memoization）后，需要存储的状态数量降至 $n+1$ 个；若采用自底向上（Bottom-up）的方式，则能显式地体现状态间的依赖顺序。

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

参考来源

MIT OpenCourseWare: Dynamic Programming I

探索关联

被引用 (1)

动态规划

同主题的其他笔记 (35)

打开关联网络

状态压缩​

示例启示​

跟踪执行与整数开销​

参考来源​