第9次内容

周子力大约 11 分钟教学文档算法设计与分析

上周回顾-动态规划之区间DP与背包DP

区间动态规划（Interval DP）是动态规划的一种常见类型，主要用于解决在一段连续区间上进行操作、合并或划分的问题。其核心思想是：先处理小区间，再逐步合并成大区间，最终求解整个区间的最优解。

一、区间DP的基本思想

状态定义：通常定义为 dp[i][j]，表示处理区间 [i, j] 时的最优值（如最小代价、最大得分等）。
转移方式：枚举区间 [i, j] 中的分割点 k（i ≤ k < j），将区间拆分为 [i, k] 和 [k+1, j]，利用子区间的最优解来更新当前区间的解：
```
dp[i][j] = min/max{ dp[i][k] + dp[k+1][j] + cost(i, j, k) }
```
其中 cost(i, j, k) 是合并两个子区间时产生的额外代价（可能与问题相关，也可能为0）。
初始化：通常对长度为1的区间（即 i == j）进行初始化，例如 dp[i][i] = 0 或某个基础值。
计算顺序：按区间长度从小到大进行遍历（长度从2到n），确保在计算 dp[i][j] 时，所有更短的子区间已经计算完毕。

二、典型应用场景

石子合并问题（经典例题）
- 有 n 堆石子排成一行，每次只能合并相邻两堆，合并代价为两堆石子数量之和，求合并成一堆的最小/最大总代价。
矩阵链乘法
- 给定一系列矩阵，确定括号化方案使得标量乘法次数最少。
回文串构造 / 最少插入次数
- 如：使字符串变为回文所需的最少插入字符数。
括号匹配类问题
- 如：合法括号序列的最大得分。

三、使用区间DP的注意事项

正确枚举区间长度
- 必须按长度递增顺序计算，否则子问题未被求解，会导致错误。
边界条件处理
- 长度为1的区间通常作为基础情况，需明确初始化。
- 注意数组下标是否从0或1开始，避免越界。
分割点的选择
- 枚举 k 时注意范围：通常是 i ≤ k < j（左闭右开），确保两个子区间非空。
合并代价的设计
- cost(i, j, k) 是否依赖于原数据？是否需要前缀和优化？
  例如石子合并中，合并 [i,j] 的代价是 sum[i..j]，可用前缀和快速计算。
时间复杂度分析
- 三层循环：外层长度 O(n)，内层起点 O(n)，分割点 O(n) → 总体 O(n³)。
- 对于 n ≤ 300~500 的问题通常可接受；若 n 更大，需考虑优化（如四边形不等式优化至 O(n²)）。
空间优化有限
- 区间DP通常难以滚动数组优化，因为 dp[i][j] 依赖多个不同长度的子区间。

四、模板代码（C++风格）


# 假设 n 是序列长度，dp 是一个 (n+1) x (n+1) 的二维列表
# 初始化 dp，通常用 0 或一个极大/极小值
dp = [[0] * (n + 1) for _ in range(n + 1)]

# 如果问题需要前缀和（如石子合并），可预先计算
# prefix = [0]
# for x in stones:
#     prefix.append(prefix[-1] + x)
# cost(i, j) = prefix[j] - prefix[i-1]

# 区间 DP 主循环：按长度递增
for length in range(2, n + 1):          # 区间长度从 2 到 n
    for i in range(1, n - length + 2):  # 起始点 i（保证 i + length - 1 <= n）
        j = i + length - 1              # 结束点 j
        dp[i][j] = float('inf')         # 初始化为极大值（求最小值时）
        # dp[i][j] = 0 或 -float('inf') 若求最大值
        for k in range(i, j):           # 枚举分割点 k ∈ [i, j-1]
            # 根据具体问题定义 cost；若无额外代价，可省略
            cost = ...                  # 例如：prefix[j] - prefix[i-1]

动态规划之背包DP

背包动态规划（Knapsack Dynamic Programming）是动态规划中一类经典问题，广泛应用于资源分配、组合优化等场景。下面从定义、解题思路和注意事项三个方面进行阐述：

一、定义

背包问题的基本设定是：
给定一个容量为 ( W ) 的背包和 ( n ) 个物品，每个物品有重量 ( w_i ) 和价值 ( v_i )。要求在不超过背包容量的前提下，选择若干物品装入背包，使得总价值最大。

根据物品是否可重复选取、是否必须装满等条件，背包问题可分为：

0-1 背包：每种物品最多选一次。
完全背包：每种物品可无限次选取。
多重背包：每种物品有数量限制（如最多选 ( c_i ) 次）。
分组背包：物品分为若干组，每组至多选一个。
二维/多维背包：物品有多个维度的“费用”（如重量和体积）。

二、解题思路

1. 状态定义

通常定义状态 ( dp[i][j] ) 表示：

考虑前 ( i ) 个物品，在背包容量为 ( j ) 时能获得的最大价值。

2. 状态转移方程

0-1 背包： [ dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j - w_i] + v_i) \quad \text{（若 } j \ge w_i\text{）} ] 不选第 ( i ) 个物品 vs 选第 ( i ) 个物品。
完全背包： [ dp[i][j] = \max(dp[i-1][j],\ dp[i][j - w_i] + v_i) ] 注意：第二个项用的是 ( dp[i][...] )，因为可以重复选。
优化空间：
由于状态只依赖前一行（0-1 背包）或当前行（完全背包），可将二维数组压缩为一维：
- 0-1 背包：倒序遍历容量（避免覆盖）
- 完全背包：正序遍历容量

3. 初始化

若不要求恰好装满：( dp[0] = 0 )，其余为 0。
若要求恰好装满：( dp[0] = 0 )，其余初始化为 ( -\infty )（表示不可达）。

4. 答案提取

通常为 ( dp[W] )（一维）或 ( \max_{j \le W} dp[j] )。

三、注意事项

遍历顺序
- 0-1 背包：容量倒序（防止重复使用同一物品）。
- 完全背包：容量正序（允许重复使用）。
边界条件
- 注意物品重量是否为 0（可能导致无限价值）。
- 容量为 0 时价值应为 0（除非有零重高价值物品）。
空间优化可行性
- 一维优化仅适用于状态转移只依赖前一状态的情形；若需记录方案（如选了哪些物品），建议保留二维数组或额外记录路径。
问题变种识别
- 有时题目并非直接给出“重量”和“价值”，需抽象建模（如：时间作为容量，收益作为价值）。
- 多维限制（如同时限制重量和体积）需扩展状态维度。
时间复杂度
- 0-1 背包：( O(nW) )
- 完全背包：( O(nW) )
- 多重背包若直接拆分物品：( O(n \cdot \max(c_i) \cdot W) )，可用二进制优化或单调队列优化。

掌握背包 DP 的关键是准确建模 + 正确设计状态转移 + 注意遍历顺序与边界。它是理解更复杂动态规划问题的重要基础。

判断属于哪类二维 DP：
- 双序列问题（如 LCS、编辑距离）→ 状态表示两个序列前缀的关系。
- 网格路径问题（如不同路径、最小路径和）→ 状态表示到达某位置的最优值。
- 矩阵局部结构（如最大正方形）→ 状态表示以某点为特定角点的形状属性。
定义状态 dp[i][j] 的精确含义（这是最关键的一步！）
✅ 好的状态定义应满足：
- 能唯一描述子问题；
- 能通过更小的子问题推导；
- 最终答案可从某个 dp[i][j] 或其组合中得出。

📌 示例：
LCS：dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度
最大正方形：dp[i][j] = 以 (i,j) 为右下角的最大正方形边长

步骤 2：推导状态转移方程

分析 dp[i][j] 如何由已知状态推出：
- 双序列：比较 s[i-1] 与 t[j-1]，分相等/不等讨论。
- 网格路径：从上方/左方转移（dp[i-1][j], dp[i][j-1]）。
- 矩阵结构：依赖邻域（如左、上、左上）。
写出清晰的转移逻辑，注意边界情况是否被覆盖。

步骤 3：确定初始化与边界条件

初始化通常包括：
- 第 0 行（dp[0][j]）：一个序列为空时的状态。
- 第 0 列（dp[i][0]）：另一个序列为空时的状态。
- 或网格的第一行/第一列（如路径问题中边界只能从一个方向来）。
技巧：使用 (m+1) × (n+1) 的 DP 表，用第 0 行/列作为“哨兵”，简化主循环逻辑。

步骤 4：确定遍历顺序

必须保证计算 dp[i][j] 时，其依赖的状态已被计算。
常见顺序：
- 双序列/网格：i 从 0 到 m，j 从 0 到 n（或 1 到 m/n）。
- 区间 DP：按区间长度从小到大（但区间 DP 通常不归为标准二维 DP）。
❌ 错误顺序会导致使用未初始化的值。

步骤 5：提取最终答案

答案可能在：
- dp[m][n]（如 LCS、编辑距离）
- max(dp[i][j])（如最大正方形）
- 某一行/列的特定位置（如地下城游戏需从右下往左上推，答案在 dp[0][0]）

步骤 6（可选）：空间优化

若 dp[i][j] 仅依赖上一行或左侧，可用滚动数组将空间从 O(mn) 降至 O(n) 或 O(min(m,n))。
但先保证正确性，再考虑优化。

二、解决二维 DP 的核心注意事项

1. 索引偏移陷阱

若 DP 表大小为 (m+1) × (n+1)，则 dp[i][j] 对应原数据的 s[i-1], t[j-1] 或 grid[i-1][j-1]。
务必检查字符/元素访问是否越界或错位。

2. 二维列表创建方式（Python 特有）

✅ 正确：dp = [[0]*n for _ in range(m)]
❌ 错误：dp = [[0]*n] * m → 所有行共享同一对象，修改一行影响全部。

3. 初始化完整性

边界（第 0 行/列）必须显式初始化，不能依赖默认值（除非默认值恰好正确）。
例如编辑距离中，dp[i][0] = i 是必须的。

4. 状态定义是否覆盖所有情况

问自己：如果两个序列都为空？一个为空？全不匹配？全匹配？极端情况是否被处理？
通过小例子（如 "" vs "a"）验证初始化和转移。

5. 操作语义的正确映射

在编辑距离中，“插入”对应 dp[i][j-1]，“删除”对应 dp[i-1][j] —— 不要混淆方向。
建议画图或写注释说明每个转移项的含义。

6. 最终答案的位置

不是所有问题答案都在 dp[-1][-1]！
- 最大正方形：需遍历整个 dp 表找最大值。
- 地下城游戏：需逆序 DP，答案在 dp[0][0]。

7. 字符 vs 整数（输入格式）

LeetCode 中矩阵常以 str（如 '1'）给出，需与 '0' 比较，而非 0。
字符串问题注意是否区分大小写、是否含特殊字符。

三、典型二维 DP 问题模板速查

问题类型	状态定义	转移特点	答案位置
LCS	`dp[i][j] = s[:i] 与 t[:j] 的 LCS 长度`	相等则 `dp[i-1][j-1]+1`，否则 `max(上, 左)`	`dp[m][n]`
编辑距离	`dp[i][j] = s[:i] → t[:j] 最少操作数`	相等则继承，否则 `1 + min(替换, 删除, 插入)`	`dp[m][n]`
网格路径	`dp[i][j] = 到 (i,j) 的路径数/最小和`	`dp[i][j] = 上 + 左`	`dp[m-1][n-1]`
最大正方形	`dp[i][j] = 以 (i,j) 为右下角的最大边长`	`1 + min(上, 左, 左上)`	`max(dp)**2`

四、总结口诀

一定义，二转移，三初始化，四顺序，五取答案。
索引偏移要小心，边界完整是关键。
状态含义说清楚，二维列表别写错。

掌握这套方法论，绝大多数二维 DP 问题都能迎刃而解。遇到新题时，先归类、再套步骤，避免盲目尝试。