12.3 动态规划回顾：重叠子问题的缓存利用

核心问题：重叠子问题如何缓存利用？
直觉：像记账本——同样的计算记录一次，下次直接查账，不重复算。

一、问题情境：如何在有限容量内装入最大价值？

想象你是仓管员，面前有一堆货物（每个货物有价值v和重量w），卡车容量有限。你希望装入价值最高的货物组合。

朴素方案：你枚举所有可能的货物组合，找价值最高的。

python

# 朴素方案：枚举所有组合（时间爆炸）
def naive_knapsack(items, capacity):
    all_combinations = []
    # 枚举所有子集：O(2^n)
    for subset in itertools.combinations(items, r):
        weight = sum(w for v, w in subset)
        if weight <= capacity:
            value = sum(v for v, w in subset)
            all_combinations.append((value, subset))
    return max(all_combinations)  # 找价值最高的

这个方案时间复杂度是O(2^n)——20个物品需要100万次枚举，30个物品需要10亿次！

思考：有没有更聪明的方法？

一个直觉浮现：同样的子问题重复计算了很多次，可以"记账"避免重复。

这就是动态规划的核心思想。

二、直觉引入：斐波那契数列的教训

2.1 分治的失败：重复计算

让我们先看一个更简单的例子：斐波那契数列。

python

def fib_divide(n):
    """
    分治思路的斐波那契（失败）
    
    时间复杂度：O(2^n)——指数爆炸！
    """
    if n <= 1:
        return n
    # 分解：fib(n) = fib(n-1) + fib(n-2)
    # 但这两个子问题有重叠！
    return fib_divide(n-1) + fib_divide(n-2)

**问题在哪？**看fib(5)的递归树：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) = 1  ← 重复计算
    │   └── fib(0) = 0  ← 重复计算
    └── fib(1) = 1      ← 重复计算

fib(3)被计算了2次，fib(2)被计算了3次，fib(1)被计算了5次！

这就是分治的禁忌——子问题重叠导致重复计算。

2.2 DP的解决方案：记账本

改进：用一个"记账本"记录已计算的结果，下次遇到同样的子问题直接查账。

python

def fib_dp_memo(n, memo=None):
    """
    DP思路的斐波那契（记忆化）
    
    时间复杂度：O(n)
    """
    if memo is None:
        memo = {}
    
    if n <= 1:
        return n
    
    # 查账：如果已经算过，直接返回
    if n in memo:
        return memo[n]
    
    # 计算，并记录到账本
    result = fib_dp_memo(n-1, memo) + fib_dp_memo(n-2, memo)
    memo[n] = result
    return result

对比：

方法	时间复杂度	fib(30)耗时
分治递归（无记忆）	O(2^n)	~10亿次计算
DP记忆化	O(n)	~30次计算

效率提升3000万倍！

2.3 什么是DP？

**动态规划（Dynamic Programming, DP）**的核心直觉是：

如果子问题会重复出现，就用一个表格（或字典）记录已计算的结果，避免重复计算。

与分治对比：

维度	分治	DP
子问题关系	独立无重叠	重叠需缓存
空间使用	无需记录中间结果	用表格记录
适用场景	无重复计算	有重复计算

三、算法定义：DP三要素

3.1 DP设计三要素

要素	名称	含义
状态	状态定义	子问题如何表示？`dp[i]` 或 `dp[i][j]` 表示什么？
转移	状态转移方程	状态之间如何推导？`dp[i] = f(dp[?])`
边界	边界条件	小规模子问题如何求解？`dp[0]` 或 `dp[i][0]`

DP模板：

python

def dp_template():
    # 1. 状态定义
    dp = [初始化]  # dp[i]表示什么
    
    # 2. 边界条件
    dp[0] = base_case
    
    # 3. 状态转移
    for i in range(1, n):
        dp[i] = f(dp[...])  # 从已求解的子问题推导
    
    # 4. 返回结果
    return dp[n]

3.2 DP正确性条件

DP能保证最优解，需要两个条件：

条件	名称	含义
最优子结构	子问题最优解组合成原问题最优解	`最优解 = 子问题最优解的组合`
重叠子问题	子问题重复出现	`重复计算 → 需缓存`

3.3 背包问题的DP设计

让我们用三要素设计背包问题的DP：

状态定义：

dp[i][w] = 前i个物品，容量为w时的最大价值

边界条件：

dp[0][w] = 0  （没有物品，价值为0）
dp[i][0] = 0  （容量为0，无法装任何物品）

状态转移：

dp[i][w] = max(
    dp[i-1][w],              # 不选第i个物品
    dp[i-1][w-weight[i]] + value[i]  # 选第i个物品
)

四、实现示例：背包问题教学化代码

4.1 01背包完整实现

python

def knapsack_dp(values, weights, capacity):
    """
    01背包问题的DP实现
    
    状态：dp[i][w] = 前i个物品容量w的最大价值
    转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i)
    边界：dp[0][w] = 0, dp[i][0] = 0
    
    参数：
    - values：物品价值列表
    - weights：物品重量列表
    - capacity：背包容量
    """
    n = len(values)
    
    # 1. 状态定义：二维DP表
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 2. 边界条件：dp[0][w] = 0 已初始化
    
    # 3. 状态转移：逐行填充
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # 不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            # 选第i个物品（如果容量足够）
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    # 4. 返回结果
    return dp[n][capacity]

# 测试
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(knapsack_dp(values, weights, capacity))  # 220

4.2 空间优化：滚动数组

二维DP表可以优化成一维：

python

def knapsack_dp_optimized(values, weights, capacity):
    """
    01背包问题的空间优化版本
    
    优化思路：
    - dp[i][w]只依赖dp[i-1][...]
    - 可以用一维数组滚动更新
    - 注意：内层循环要逆序（避免覆盖）
    """
    n = len(values)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 逆序更新：避免使用本轮已更新的值
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# 测试
print(knapsack_dp_optimized(values, weights, capacity))  # 220

为何逆序？

正序更新（错误）：
dp[0] → dp[10] → dp[20] → dp[30] → ...
问题：dp[20]可能使用了dp[10]（本轮已更新），而非dp[i-1][10]

逆序更新（正确）：
dp[50] → dp[40] → dp[30] → ...
正确：dp[30]使用dp[10]（本轮未更新），即dp[i-1][10]

五、复杂度分析：时间与空间

5.1 时间复杂度

01背包：O(n × W)

计算过程：
- 状态数：(n+1) × (W+1)
- 每个状态的转移成本：O(1)
总复杂度：O(n × W)

对比朴素方案：

算法	时间复杂度	20个物品W=1000
枚举所有组合（朴素）	O(2^n)	100万次
DP	O(n × W)	2000次

DP让效率提升500倍！

5.2 空间复杂度

01背包：

实现	空间复杂度
二维DP	O(n × W)
一维优化	O(W)

六、与前章节关联：DP在哪里出现过？

6.1 DP前章节应用

章节	DP应用	说明
Ch6	背包问题、LIS、编辑距离	DP专题
Ch4	最短路径（Bellman-Ford）	DP在图上的应用
Ch4	所有节点间最短路径（Floyd-Warshall）	DP在高维的应用
Ch5	回溯对比	DP求最优解，回溯求所有解

6.2 LIS：另一经典DP问题

最长递增子序列（LIS）：给定数组，找最长递增子序列长度。

python

def lis_dp(arr):
    """
    LIS的DP解法
    
    状态：dp[i] = 以arr[i]结尾的LIS长度
    转移：dp[i] = max(dp[j] + 1) for j < i and arr[j] < arr[i]
    边界：dp[i] = 1（每个元素至少长度1）
    """
    n = len(arr)
    dp = [1] * n
    
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 测试
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_dp(arr))  # 4 ([2, 3, 7, 101])

七、设计反思：DP的失败案例

7.1 失败案例1：无重叠子问题

问题：矩阵乘法的最优顺序。

DP尝试：

python

def matrix_chain_dp(matrices):
    """
    矩阵链乘的DP解法
    
    状态：dp[i][j] = 矩阵i到j的最少乘法次数
    轶移：dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i,k,j))
    
    问题：这个DP是正确的！
    因为子问题重叠（子矩阵链会重复计算）
    """
    n = len(matrices)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

这个DP是成功的，因为子问题重叠。

但有些问题无重叠子问题，DP无用：

反例：汉诺塔问题

汉诺塔：递归解法必须O(2^n)

分析：
每次递归：move(n-1) → move(1) → move(n-1)
子问题不重叠：
- 第一次move(n-1)和第二次move(n-1)是不同的子问题（起始柱不同）
- 无法缓存复用

DP无用，分治也无法优化（问题本质）

7.2 失败案例2：状态爆炸

问题：最长简单路径（无重复节点的最长路径）。

DP尝试：

python

# 错误的DP尝试
def longest_simple_path_wrong(graph, start, end):
    """
    状态：dp[u][v] = u到v的最长简单路径
    
    问题：状态定义后，转移方程无法正确计算
    因为：最长简单路径需要记录路径中的节点（避免重复）
    状态需要：dp[u][v][visited_set] → 状态爆炸！
    """
    # 状态空间：O(V^2 × 2^V) —— 指数爆炸
    pass

失败原因：状态需要记录路径信息，状态空间指数爆炸。

正确解法：回溯（见12.4节）

7.3 失败总结：DP的三禁忌

禁忌	现象	正确范式
无重叠子问题	子问题不重复出现	分治
状态爆炸	状态空间指数级	回溯或近似算法
无法定义有效状态	找不到好的状态表示	重新建模

八、知识卡片

C12-17 DP三要素

直觉解释：状态是"记录什么"，转移是"怎么推导"，边界是"从哪开始"。

核心内容：

要素	含义
状态	子问题表示：dp[i] 或 dp[i][j]
转移方程	状态间关系：dp[i] = f(dp[?])
边界条件	初始值：dp[0]

关键特征：三要素缺一不可，状态定义决定转移复杂度。

常见误解：

❌ 状态数越少越好——状态设计不当会导致转移困难
✅ 正确理解：状态数和转移成本要平衡

实例：背包问题——状态 dp[i][w] 表示前i个物品容量w的最大价值。

C12-18 DP正确性证明

直觉解释：证明"每一步都算对了，最后结果必然对"。

核心内容：

最优子结构（子问题最优解组合成原问题最优解）
重叠子问题（子问题重复出现）

关键特征：数学归纳法——边界正确 + 假设子问题正确 + 证明转移正确。

常见误解：

❌ DP一定得到最优解——需要证明最优子结构成立
✅ 正确理解：DP正确性依赖最优子结构

实例：LCS——证明 LCS(i,j) = LCS(i-1,j-1)+1 或 max(LCS(i-1,j), LCS(i,j-1))。

C12-19 DP空间优化

直觉解释：只记住"有用的"，不记住"过期的"。

核心内容：

技术	适用场景	空间改善
滚动数组	转移只依赖前一状态	O(n²) → O(n)
状态压缩	01背包	O(nW) → O(W)

关键特征：空间复杂度 = 状态空间大小，可优化维度。

常见误解：

❌ 空间优化不影响时间——某些优化可提高缓存命中率
✅ 正确理解：空间优化可能间接提升时间效率

实例：01背包从 dp[n][W] 优化到 dp[W]，注意内层循环逆序。

C12-20 DP时间优化

直觉解释：减少"无效计算"，提高"有效转移效率"。

核心内容：

技术	适用场景	时间改善
单调队列优化	滑动窗口最值	O(nk) → O(n)
斜率优化	决策单调性	O(n²) → O(n log n)

关键特征：时间复杂度 = 状态数 × 转移成本。

常见误解：

❌ 优化状态转移比优化状态数更重要——通常减少状态数效果更大
✅ 正确理解：先优化状态数，再优化转移成本

实例：单调队列优化滑动窗口最值。

C12-21 DP vs 分治

直觉解释：DP记住"算过的"，分治"算完就扔"。

核心内容：

维度	DP	分治
子问题关系	重叠需缓存	独立无需缓存
空间使用	用表格记录	无需记录

关键特征：DP用空间换时间；分治无重复计算。

常见误解：

❌ DP是"加强版分治"——它们解决的问题类型不同
✅ 正确理解：DP和分治适用条件不同

实例：斐波那契——分治O(2^n)；DP缓存O(n)。

C12-22 DP vs 贪心

直觉解释：DP"看全局"，贪心"只看眼前"。

核心内容：

维度	DP	贪心
后效性	有后效性（需考虑所有状态转移）	无后效性（当前不影响未来）
选择	每步考虑所有可能转移	每步唯一选择

关键特征：DP求全局最优保证；贪心求全局最优需条件。

常见误解：

❌ DP总是比贪心慢——DP可能O(n)，贪心O(n log n)
✅ 正确理解：DP和贪心复杂度需具体分析

实例：背包问题——DP保证最优；贪心可能非最优。

C12-23 DP失败案例

直觉解释：DP不是万能的，有些问题不适合DP。

核心内容：失败原因：

子问题不重叠（不如用分治）
状态爆炸（空间不可接受）
无法定义有效状态

关键特征：强行DP会导致状态空间指数爆炸。

常见误解：

❌ DP能解决所有优化问题——错！要看是否有重叠子问题和最优子结构
✅ 正确理解：DP适用有严格条件

实例：最长简单路径——状态需要记录路径信息，状态爆炸。

C12-24 DP直觉建立

直觉解释：看到"多次重复计算同样子问题"，想DP缓存。

核心内容：判断DP适用的直觉问题：

子问题会重复出现吗？
能定义状态吗？
转移方程能写吗？

关键特征：抓住"重叠子问题"的本质，用表格避免重复计算。

常见误解：

❌ DP就是填表——关键在于状态定义和转移方程设计
✅ 正确理解：状态定义是DP设计的关键

实例：最短路径的DP直觉——dist[i] = min(dist[j] + edge[j][i])。

九、练习设计

基础练习（理解DP）

练习 12.3-1：用DP解决编辑距离问题。

提示：

编辑距离：将字符串A转换成B的最少操作次数（插入、删除、替换）。

状态：dp[i][j] = A前i字符转换成B前j字符的最少操作数
转移：
dp[i][j] = min(
    dp[i-1][j] + 1,       # 删除A[i]
    dp[i][j-1] + 1,       # 插入B[j]
    dp[i-1][j-1] + cost   # 替换（cost=0 if A[i]==B[j] else 1）
)
边界：dp[0][j] = j, dp[i][0] = i

练习 12.3-2：分析LIS的空间优化。

答案：

LIS的标准DP：O(n)空间（一维）

优化思路：
- dp[i]只依赖dp[...]（小于i的所有状态）
- 无法像01背包那样滚动优化（依赖范围不确定）

但可以用"贪心+二分"优化到O(n log n)时间：
维护一个数组tails，tails[k] = 长度k的LIS的最小结尾元素
每次更新：用二分查找确定插入位置

进阶练习（DP应用）

练习 12.3-3：设计DP解决最长公共子序列（LCS）。

思路：

python

def lcs_dp(s1, s2):
    """
    LCS的DP解法
    
    状态：dp[i][j] = s1前i字符和s2前j字符的LCS长度
    转移：
    dp[i][j] = max(
        dp[i-1][j],
        dp[i][j-1],
        dp[i-1][j-1] + 1 if s1[i-1] == s2[j-1]
    )
    边界：dp[0][j] = 0, dp[i][0] = 0
    """
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if s1[i-1] == s2[j-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
    
    return dp[n][m]

设计练习（DP vs 分治 vs 贪心）

练习 12.3-4：对比三种范式在"活动选择问题"上的解法。

分析：

活动选择：选最多不重叠活动

贪心解法：
按结束时间排序，每次选最早结束的不重叠活动
O(n log n)

DP解法：
dp[i] = 以活动i结束的最大活动数
转移：dp[i] = max(dp[j] + 1) for j < i and activity[j]不重叠activity[i]
O(n²)

分治解法：
无法有效分治（子问题不独立）

结论：贪心最优（条件满足），DP次优，分治失败

开放练习

练习 12.3-5：LLM的Beam Search如何体现DP思想？

思考方向：

Beam Search：
每步保留top-k候选，而非贪心的top-1

DP视角：
状态：(位置i, 前i个token序列)
转移：扩展每个候选序列，保留top-k
复杂度：O(n × k × vocab_size)

与贪心对比：
贪心：每步唯一选择（O(n × vocab_size)）
Beam Search：每步保留k个候选（O(n × k × vocab_size))

Beam Search是DP的近似：
- 完整DP：保留所有候选（状态爆炸）
- Beam Search：只保留top-k候选（近似DP）

导航：上一节：12.2 贪心回顾 | 下一节：12.4 回溯回顾 →

12.3 动态规划回顾：重叠子问题的缓存利用 ​

一、问题情境：如何在有限容量内装入最大价值？ ​

二、直觉引入：斐波那契数列的教训 ​

2.1 分治的失败：重复计算 ​

2.2 DP的解决方案：记账本 ​

2.3 什么是DP？ ​

三、算法定义：DP三要素 ​

3.1 DP设计三要素 ​

3.2 DP正确性条件 ​

3.3 背包问题的DP设计 ​

四、实现示例：背包问题教学化代码 ​

4.1 01背包完整实现 ​

4.2 空间优化：滚动数组 ​

五、复杂度分析：时间与空间 ​

5.1 时间复杂度 ​

5.2 空间复杂度 ​

六、与前章节关联：DP在哪里出现过？ ​

6.1 DP前章节应用 ​

6.2 LIS：另一经典DP问题 ​

七、设计反思：DP的失败案例 ​

7.1 失败案例1：无重叠子问题 ​

7.2 失败案例2：状态爆炸 ​

7.3 失败总结：DP的三禁忌 ​

八、知识卡片 ​

C12-17 DP三要素 ​

C12-18 DP正确性证明 ​

C12-19 DP空间优化 ​

C12-20 DP时间优化 ​

C12-21 DP vs 分治 ​

C12-22 DP vs 贪心 ​

C12-23 DP失败案例 ​

C12-24 DP直觉建立 ​

九、练习设计 ​

基础练习（理解DP） ​

进阶练习（DP应用） ​

设计练习（DP vs 分治 vs 贪心） ​

开放练习 ​

12.3 动态规划回顾：重叠子问题的缓存利用

一、问题情境：如何在有限容量内装入最大价值？

二、直觉引入：斐波那契数列的教训

2.1 分治的失败：重复计算

2.2 DP的解决方案：记账本

2.3 什么是DP？

三、算法定义：DP三要素

3.1 DP设计三要素

3.2 DP正确性条件

3.3 背包问题的DP设计

四、实现示例：背包问题教学化代码

4.1 01背包完整实现

4.2 空间优化：滚动数组

五、复杂度分析：时间与空间

5.1 时间复杂度

5.2 空间复杂度

六、与前章节关联：DP在哪里出现过？

6.1 DP前章节应用

6.2 LIS：另一经典DP问题

七、设计反思：DP的失败案例

7.1 失败案例1：无重叠子问题

7.2 失败案例2：状态爆炸

7.3 失败总结：DP的三禁忌

八、知识卡片

C12-17 DP三要素

C12-18 DP正确性证明

C12-19 DP空间优化

C12-20 DP时间优化

C12-21 DP vs 分治

C12-22 DP vs 贪心

C12-23 DP失败案例

C12-24 DP直觉建立

九、练习设计

基础练习（理解DP）

进阶练习（DP应用）

设计练习（DP vs 分治 vs 贪心）

开放练习