序列与字符串动态规划
本节目标
用前缀、末尾位置和双串前缀刻画序列匹配、拆分、计数与编辑。
识别信号
输入是数组、括号串或两个字符串，答案由前缀能否完成、末尾位置的最优值、两个前缀的关系或选取方案数决定时，状态的坐标通常就是位置或前缀长度。
状态定义与转移推导
LIS 令状态表示以某位置结尾的最长递增长度；单词拆分令状态表示前缀是否可达；双串题令 dp[i][j] 表示两个前缀的答案。括号题让状态表示以右端点结尾的有效长度；子序列计数让状态表示匹配目标前缀的方案数。
初始化与遍历顺序
空前缀是关键边界：可达性中 dp[0] 为真，编辑距离的第一行和第一列是插删次数，计数中空目标有一条方案。二维最优值通常从左上到右下；一维计数压缩后必须倒序更新，避免同一源字符被重复使用。
通用模板
先确定状态覆盖的前缀或末尾位置
枚举当前字符或位置
匹配时从更短前缀转移
不匹配时在合法前驱中取最优或保持不可达
最后读取完整前缀对应的状态
空间优化与复杂度
LIS 的位置状态为 O(n²) 时间、O(n) 空间。双串 DP 常为 O(mn) 时间空间，可按依赖关系压缩一维；是否压缩取决于是否需要恢复路径，以及更新顺序能否保持上一行信息。
母题序列
- 最长递增子序列（必学）：枚举所有更早且更小的前驱位置。
- 单词拆分（必学）：把可达前缀接上一个字典词。
- 最长公共子序列（必学）：比较两个前缀的最后字符。
- 编辑距离（必学）：用替换、插入和删除统一不匹配。
- 最长有效括号（必学）：把成对括号和前段有效区间拼接。
- 不同的子序列（拓展）：统计从源串选出目标串的全部方案。
常见误区
- 把子序列误当子串，错误地要求字符连续。
- 忘记空前缀初始化，导致首个字符无法转移。
- 一维计数正序更新，令一个源字符在同轮被选多次。
- 括号题只配对相邻字符，遗漏可拼接的有效区间。
迁移方向
前缀状态加入容量后成为背包；两个区间相互切分时成为区间 DP；若必须同时记住已使用元素集合，则需要状态压缩 DP。