动态规划 · HTML
数学 / 逻辑形态
单序列：dp[i]=以 i 结尾的最优子序列，枚举 j<i 且 compatible(j,i)。双序列：dp[i][j]=前缀 A[:i],B[:j] 的答案，相等时匹配，否则跳过一侧/执行编辑。
识别信号
- 可以删除/跳过元素但不能改变相对顺序。
- 目标涉及最长递增、公共子序列、编辑或匹配。
- 最后选中的位置能划分子问题。
- 两个字符串/序列的前缀索引足以描述未来。
- 不同选择历史汇合到相同末端或前缀对。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 连续子数组/子串 | 连续性通常用滑动窗口、前缀和或局部 DP，不应允许随意跳过。 |
| 只需判断模式是否为子序列 | 一次查询可双指针线性完成，无需二维 DP。 |
| 集合匹配无顺序 | 若相对顺序不重要，哈希/计数或二分图匹配可能更合适。 |
核心不变量
每个已计算状态严格对应其末端/前缀定义，并已考虑所有合法的最后匹配、跳过或编辑动作。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 单序列末端 i，或两个前缀长度 (i,j)；可附 parent/action 恢复具体序列。 |
| Transition | 从最后动作反推：匹配两末项、跳过 A 末项、跳过 B 末项，或执行替换/插入/删除并聚合。 |
| Frontier / order | 按增大 i（以及 j）的 DAG 顺序填表；二维状态可按行滚动，但恢复路径通常需完整信息。 |
Python 骨架
def lcs_length(a, b):
prev = [0] * (len(b) + 1)
for x in a:
cur = [0]
for j, y in enumerate(b, 1):
if x == y:
cur.append(prev[j - 1] + 1)
else:
cur.append(max(prev[j], cur[-1]))
prev = cur
return prev[-1]
正确性思路
- 空前缀与任何序列的公共子序列长为 0。
- 末项相等时存在最优解匹配它们并加到更短前缀；不等时任一最优解至少跳过一个末项。
- 转移覆盖这些互斥最后动作，按前缀长度归纳得到正确答案。
复杂度
| Time | Space | Parameters |
|---|
| 典型双序列 O(mn)；单序列朴素 O(n²) | 长度可滚动到 O(min(m,n))；恢复路径常 O(mn) | m/n 为序列长度。 |
边界条件
- 空序列
- 重复元素
- 相等判定/大小写
- 只要长度还是具体序列
- 滚动行方向
- 编辑代价非均匀
错误模式
| Pattern | Why it fails / fix |
|---|
| 子序列与子串混淆 | 子序列可跳过；状态和转移必须允许不连续。 |
| 相等时仍漏算跳过分支 | 需根据具体目标证明匹配末项安全；泛化代价下可能仍要比较其他动作。 |
| 滚动数组引用同一列表 | prev/cur 必须代表不同层，避免本行污染上一行。 |
| 只存长度却要求恢复 | 需保存 parent、完整表或用额外分治重构。 |
选择与排除规则
- 先判断连续还是可跳过。
- 一句话定义以 i 结尾或前缀对状态。
- 按最后动作列全转移。
- 只要长度才压缩空间；要路径保留重构信息。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 长度为 2，可取 'cb' 或 'ab'。 |
| Setup | A='cab'，B='acb'，求公共子序列长度。 |
| Trace | 末尾 b 相同，可从前缀 'ca' 与 'ac' 的答案 1 加一。 |
Recall prompts
我的补充