动态规划入门：从状态定义到最优方案恢复
插画：tokki
有些选择会排除后面的机会，另一些选择收益较低却能与更多活动组合。要最大化总收益，可以把大问题拆成一组有明确含义的较小问题，并保存它们的答案。
本文沿着带权区间调度理解状态、转移、初始化、重叠子问题和方案恢复。需要熟悉贪心篇的活动模型，并了解数组、循环及函数调用。
1. 从一次选择转向比较子问题
贪心篇的带权反例得到：按最早结束选择b、e、h，数量为3、收益41；而d、h收益42。无权问题中保持数量不变的交换，可能改变权重。
动态规划比较所有合法方案的类别，并通过复用子问题答案避免反复求解。这里的关键是：用哪个状态描述“剩下还有哪些选择”？
2. 带权任务与前驱
沿用Introduction第27至28页的8个区间及权重，统一数据如下。活动为半开区间，起点严格小于终点；端点相接兼容。
| 任务 | 开始时间 | 结束时间 | 权重 |
|---|---|---|---|
| a | 0 | 6 | 23 |
| b | 1 | 4 | 12 |
| c | 3 | 5 | 20 |
| d | 3 | 8 | 26 |
| e | 4 | 7 | 13 |
| f | 5 | 9 | 20 |
| g | 6 | 10 | 11 |
| h | 8 | 11 | 16 |
按结束时间排序为b、c、a、e、d、f、g、h。编号j从1开始，数组实现中第j项位于j−1。
3. 状态与转移怎样得到
仍按结束时间排序，并用 $j=1,\ldots,n$ 给任务重新编号。
- $OPT(j)$：只允许从前 j 个任务中选择时，能得到的最大总权重。
- $p(j)$：排在 j 前面、结束时间不晚于 j 的开始时间的最大编号；不存在时取0。
- $OPT(0)=0$：没有任务可以选时，收益为0。
为什么只要记住一个前驱编号？因为结束时间有序，与 j 兼容的前面任务恰好形成一个前缀，编号不超过 $p(j)$。
3.1 为什么只有选与不选两类
不选 j，只能从前 j-1 个任务中选择，最优值为 $OPT(j-1)$。
选 j，则所有同时选的更早任务都必须在 j 开始前结束，最优收益为 $v_j+OPT(p(j))$。
两种情况覆盖全部可行方案，因此：
$$ OPT(j)=\max\bigl(OPT(j-1),\ v_j+OPT(p(j))\bigr) $$这个转移来自对所有最优方案的两类划分。
3.2 六个概念在本例中的对应
| 概念 | 在当前问题中的含义 |
|---|---|
| 状态 | OPT(j)描述只考虑前j个任务的最大收益 |
| 子问题 | 选j后求OPT(p(j))，不选j后求OPT(j−1) |
| 最优子结构 | 已确定选或不选j后，相应前缀也必须取得最优收益 |
| 重叠子问题 | 不同分支可能再次请求同一个OPT(k) |
| 转移 | 比较两类方案的最好收益，取最大 |
| 初始化 | 没有任务时OPT(0)=0，允许空方案 |
例如选j后，如果前p(j)项使用的不是最优兼容方案，就可以换成更高收益的前缀，与j组合后改进整体，违背最优性。这是本题最优子结构的理由。
3.3 为什么递归会重复工作
求OPT(8)会请求OPT(5)和OPT(7)；OPT(7)继续请求OPT(6)，而OPT(6)又会请求OPT(5)。同一个OPT(5)被不同路径重复计算。
朴素递归只表达转移，每次遇到同一状态都会重新求解。记忆化递归把已算结果存起来；自底向上的DP则按j=0、1、…、n依次填表。由于p(j)<j，每个依赖在填当前行前都已完成。
4. 手动填完八个状态
| j | 任务 | 区间 | 权重 | p(j) | 选当前任务 | 不选当前任务 | OPT(j) |
|---|---|---|---|---|---|---|---|
| 0 | 无 | 无 | 0 | 无 | 无 | 无 | 0 |
| 1 | b | $[1,4)$ | 12 | 0 | 12+0=12 | 0 | 12 |
| 2 | c | $[3,5)$ | 20 | 0 | 20+0=20 | 12 | 20 |
| 3 | a | $[0,6)$ | 23 | 0 | 23+0=23 | 20 | 23 |
| 4 | e | $[4,7)$ | 13 | 1 | 13+12=25 | 23 | 25 |
| 5 | d | $[3,8)$ | 26 | 0 | 26+0=26 | 25 | 26 |
| 6 | f | $[5,9)$ | 20 | 2 | 20+20=40 | 26 | 40 |
| 7 | g | $[6,10)$ | 11 | 3 | 11+23=34 | 40 | 40 |
| 8 | h | $[8,11)$ | 16 | 5 | 16+26=42 | 40 | 42 |
例如计算 h 时，$p(8)=5$ 表示 d 恰好在时间8结束。选择 h 可以接上前5个任务的最优方案，而不是只能接“单个前驱任务 d”；只是本例中这个前缀的最优方案恰好只有 d。
5. 从最优值恢复任务方案
从最后一行往回看：
- $16+OPT(5)=42>OPT(7)=40$，选 h，跳到第5行。
- $26+OPT(0)=26>OPT(4)=25$，选 d，跳到第0行。
- 结束，按时间顺序返回 d、h。
平局时可以选择任一达到同样收益的方案。下面的程序统一采用“平局不选当前项”，填表与回溯保持同一规则。
6. Python实现
每项是(名称, 开始, 结束, 权重)，名称在例子中唯一。代码保留排序、前驱数组、收益数组与回溯的完整过程。
from bisect import bisect_right
def order_jobs(jobs):
ordered = sorted(jobs, key=lambda job: (job[2], job[1], job[0]))
if any(start >= finish for _, start, finish, _ in ordered):
raise ValueError("Each job must have start < finish")
return ordered
def weighted_interval_scheduling(jobs):
ordered = order_jobs(jobs)
finishes = [job[2] for job in ordered]
n = len(ordered)
previous = [0] * (n + 1)
best = [0] * (n + 1)
for j, (_, start, _, weight) in enumerate(ordered, start=1):
# The eligible prefix ends strictly before the current array entry.
previous[j] = bisect_right(finishes, start, 0, j - 1)
best[j] = max(best[j - 1], weight + best[previous[j]])
selected = []
j = n
while j > 0:
name, _, _, weight = ordered[j - 1]
if weight + best[previous[j]] > best[j - 1]:
selected.append(name)
j = previous[j]
else:
j -= 1
selected.reverse()
return selected, best[n]
jobs = [
("a", 0, 6, 23),
("b", 1, 4, 12),
("c", 3, 5, 20),
("d", 3, 8, 26),
("e", 4, 7, 13),
("f", 5, 9, 20),
("g", 6, 10, 11),
("h", 8, 11, 16),
]
print(weighted_interval_scheduling(jobs))
assert weighted_interval_scheduling(jobs) == (["d", "h"], 42)
assert weighted_interval_scheduling([]) == ([], 0)输出(['d', 'h'], 42)。
6.1 bisect_right为什么给出前驱
finishes按结束时间升序排列。bisect_right(finishes, start, 0, j - 1)返回当前任务之前结束时间不大于start的元素个数，恰好是以1为起点的前驱编号。
右侧插入位置包含“结束等于开始”的情况。hi=j-1是Python的右开边界，把当前数组位置j−1排除，保证p(j)<j。
previous[j]保存兼容前缀的长度，而非最终方案里必须选中的那项任务。best[j]只保存最大收益，回溯才恢复任务名称。
7. 时间与空间
| 阶段 | 次数与成本 | 上界 |
|---|---|---|
| 排序 | n项比较排序 | O(n log n) |
| 前驱 | 每项二分查找 | O(n log n) |
| 填表 | n个状态，每次常数个比较与索引 | O(n) |
| 回溯 | j每轮严格下降 | O(n) |
| 额外空间 | 排序列表、finishes、previous、best与结果 | O(n) |
总时间O(n log n)，额外空间O(n)。若前驱已经给出，单独的填表与回溯是线性的。时间与空间的口径见复杂度分析。
8. 动态规划的思考顺序
- 用一句完整的话定义状态，注明允许选择的范围与返回含义。
- 找出最后一步或当前对象的所有选择类别。
- 对每类写出代价与依赖状态，确认没有遗漏可行最优方案。
- 写初始化和边界，如OPT(0)=0。
- 按依赖确定计算顺序；本题所有依赖编号更小。
- 用“状态数×每状态工作量”分析DP，再加预处理与恢复成本。
- 确定只需最优值，还是还要保存或恢复实际方案。
背包问题还需要容量维度，最长递增子序列需要说明“以哪个元素结尾”。状态的含义决定哪些历史信息要保留。
9. 易错点
p(j)是兼容前缀的边界，并不要求方案一定选第p(j)项。选j后回到p(j)，而不是j−1；后者可能包含与j冲突的任务。OPT(0)表示空前缀，不是原数组的第一个活动。最优子结构说明转移正确，重叠子问题说明保存答案能节省计算，两者承担不同作用。
10. 练习
练习1：四项任务
A=[0,3)，B=[1,2)，C=[2,4)，D=[4,5)，权重分别10、4、4、3。写出排序、前驱、DP表和一个最优方案。
练习2：最优值与方案
只返回OPT(n)是否已经返回实际最优解？回溯选j后为何跳到p(j)？
练习3：前驱与实际选择
八任务例中p(8)=5。它表示选h后必须选d，还是允许使用前5项中的最优兼容方案？
练习4：初始化与平局
输入为空时返回什么？两个冲突任务权重相同，选择“不选当前项”是否损失收益？
练习5：预处理成本
已经得到p(j)后，DP只需O(n)。能否因此说整个带权区间调度程序也是O(n)？
11. 参考答案
练习1解析
| j | 任务 | 权重 | p(j) | 选当前任务 | 不选当前任务 | OPT(j) |
|---|---|---|---|---|---|---|
| 0 | 无 | 0 | 无 | 无 | 无 | 0 |
| 1 | B | 4 | 0 | 4 | 0 | 4 |
| 2 | A | 10 | 0 | 10 | 4 | 10 |
| 3 | C | 4 | 1 | 4+4=8 | 10 | 10 |
| 4 | D | 3 | 3 | 3+10=13 | 10 | 13 |
回溯：选择D，跳到第3行；跳过C，退到第2行；选择A，结束。因此最优方案是A、D，总权重13。D的前驱是C所在的前缀，但不要求最终方案一定包含C。
练习2至5解析
- OPT(n)是值；方案还需要任务集合。选j后，编号p(j)+1至j−1都与j冲突，只能回到兼容前缀p(j)。
- 后者。前缀最优解可以由多项组成，本例前5项的最优方案恰为d。
- 空输入返回([],0)。平局两类收益相同，跳过当前项仍保留一个最优方案；回溯应采用相同规则。
- 不能。排序和二分前驱计算仍是O(n log n)，总复杂度应包含它们。
12. 后续学习与资料
上一篇：贪心算法；下一篇：图上的组合优化。最优性证明的交换结构可回看贪心篇，状态数与辅助空间分析可回看复杂度基础。
参考：Introduction第28页的带权区间调度；02Analysis第58至68页的状态、朴素递归、记忆化与自底向上DP。完整手算表、Python实现和四任务练习沿用原笔记。
