什么是动态规划（memoization vs tabulation）？

Question

Accepted Answer

**Dynamic programming (DP)** 通过计算每个子问题一次并重复使用结果来解决具有**重叠子问题**和**最优子结构**的问题。两种方式是 **memoization**（自顶向下）和 **tabulation**（自底向上）。

## 概念

朴素递归会指数级地重新计算相同的子问题。DP 将它们缓存起来，把指数级的工作量转化为多项式级。

## Memoization（自顶向下）

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## Tabulation（自底向上）

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## Memoization vs tabulation

| | Memoization | Tabulation |
|---|------------|------------||
| 方向 | 自顶向下递归 | 自底向上迭代 |
| 计算 | 仅必要的状态 | 所有状态 |
| 风险 | 栈溢出 | 无 |
| 空间 | 可以优化 | 通常可降至 O(1) 行 |

## 复杂度

Fibonacci：从 O(2ⁿ) 朴素版本到 **O(n)** 时间，O(n)（或 O(1)）空间。

## 何时使用 / 陷阱

当子问题**重叠**时使用 DP。仔细定义状态和递推关系——这是难点。如果子问题不重叠，普通的分治法就足够了。

## 为什么这很重要

DP 将难以处理的指数级问题——最短路径、编辑距离、背包问题——转化为高效的算法。

识别状态和递推关系的技能是算法面试中最受重视的能力之一。

它是从 diff 工具到生物信息学序列比对等实际系统的基础。