第 102 章 线性 DP¶
本章配套 24 道例题，见 §例题。
「线性 DP」指状态沿一个（或两个）序列维度推进的 DP。它是笔试出现最多的 DP 形态， 四个经典模型：最大子段和、LIS、LCS、编辑距离。
1 最大子段和（Kadane）¶
选一个非空连续子数组使元素和最大。
设 \(f_i\) = 「以 \(i\) 结尾」的最大子段和。枚举最后一步：这一段要么把前面接上，要么从 \(i\) 重开。
答案 \(= \max_i f_i\)。
等价视角：前缀和¶
一边扫一边记录历史最小前缀和。两种写法完全等价，前缀和视角在带长度限制 （如「长度不超过 \(k\) 的最大子段和」）时更容易扩展成单调队列，见 DP优化。
BISHI134 最大子段和（简单）¶
\(n \le 2\times10^5\)，\(a_i\) 可为负。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
# cur = 以当前元素结尾的最大子段和；best = 扫到目前为止的全局最优
best = cur = a[0] # ★ 初值必须是 a[0]，不能是 0
for i in range(1, n):
x = a[i]
# cur > 0 才值得把前面那段接上；否则从 x 处重开一段
cur = x + cur if cur > 0 else x
if cur > best: # 每个位置都可能是答案的右端点，逐个比一遍
best = cur
print(best)
main()
坑 1（最重要）：题目要求非空，所以答案初值必须是 \(a_1\)（或 \(-\infty\)），不能是 0。 全负数组时答案是最大的那个负数；初值取 0 会错误地输出 0。
坑 2：
max(f, 0)里的 0 是「放弃前面这段」，不是「和为 0 的空段」—— 因为 \(f_i\) 里必定含 \(a_i\)，非空性有保证。
题解：solutions/nowcoder/BISHI134/sol.py（已通过官方样例验证）
2 最长上升子序列（LIS）¶
\(O(n^2)\) 朴素 DP¶
\(f_i\) = 以 \(i\) 结尾的最长上升子序列长度：
\(n \le 1000\) 时可用；\(n = 5000\) 时 \(2.5\times10^7\) 次 Python 迭代就危险了。
\(O(n\log n)\) 贪心 + 二分¶
维护数组 tails，tails[i] = 长度为 \(i+1\) 的上升子序列结尾元素的最小可能值。
关键性质：tails 天然单调不减。新元素 \(x\) 来时：
- 在
tails里找第一个「不该被 \(x\) 挤掉」的位置 \(p\)，用 \(x\) 替换它 （让同长度的结尾更小、更有潜力）； - 若不存在（\(x\) 比所有元素都大）⇒
append，答案长度 \(+1\)。
等号位置：四个变体的完整对照¶
这是 LIS 唯一会写错的地方，把四种情况列全：
| 目标 | 找第一个 | 函数 | 记忆法 |
|---|---|---|---|
| 最长严格上升 | \(\ge x\) 的位置 | bisect_left |
相等的元素应该被挤掉 ⇒ left |
| 最长不下降（允许相等） | \(> x\) 的位置 | bisect_right |
相等的元素不该被挤掉，越过它们 ⇒ right |
| 最长严格下降 | 对 \(-x\) 求严格上升 | bisect_left on [-x] |
取负翻转方向 |
| 最长不上升 | 对 \(-x\) 求不下降 | bisect_right on [-x] |
同上 |
# [片段]
from bisect import bisect_left, bisect_right
tails = [] # tails[i] = 长度为 i+1 的上升子序列的最小结尾值
for x in a:
p = bisect_right(tails, x) # 不下降；严格上升改 bisect_left
if p == len(tails): # x 比现有全部结尾都大 ⇒ 能接出更长的一条
tails.append(x)
else:
tails[p] = x # 同长度换个更小的结尾，后面更容易接上新元素
answer = len(tails) # tails 的长度就是最长长度（内容不是答案序列）
tails不是答案序列本身，只是「每个长度的最优结尾值」，不能拿它去还原方案。 要还原方案需要额外记录每个元素被放到了哪个位置，再回溯。Python 3.9 的
bisect不支持key参数（3.10 才加）。 对元组或对象排序时要么预先构造键数组，要么取负。
BISHI133 最长不下降子序列（简单）¶
\(n \le 5\times10^3\)。
\(n\) 只有 5000，\(O(n^2) = 2.5\times10^7\) 在 2 秒里也悬，而 \(O(n\log n)\) 只有 \(6\times10^4\) 次操作，稳。
import sys
from bisect import bisect_right
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
tails = [] # 始终单调不减，所以可以直接二分
for i in range(1, n + 1): # 数据从下标 1 开始，data[0] 是 n
x = int(data[i])
p = bisect_right(tails, x) # 「不下降」用 right：跳过与 x 相等的那些结尾
if p == len(tails): # 找不到可替换的位置 ⇒ 答案长度加一
tails.append(x)
else:
tails[p] = x # 把长度 p+1 的结尾压得更小
print(len(tails))
main()
题解：solutions/nowcoder/BISHI133/sol.py（已通过官方样例验证）
与 Dilworth 定理的联系¶
「最少用几个不上升子序列覆盖整个序列」的答案 等于 「最长上升子序列的长度」。 这是 Dilworth 定理的直接推论，也是 NOIP 导弹拦截问题的第二问。 证明见 偏序集与Dilworth定理。
3 最长公共子序列（LCS）¶
两个序列 \(a\)（长 \(n\)）、\(b\)（长 \(m\)）：
\(O(nm)\)。Python 下 \(n = m = 1000\) 是 \(10^6\) 次迭代，勉强；\(n = m = 5000\) 就不行了。
Python 优化：滚动成一维，并把内层用 map 批处理。但 LCS 的转移有串行依赖
（\(f[i][j]\) 依赖 \(f[i][j-1]\)），不能直接 map。可行的做法：
# [片段]
# 只求长度时，按 b 的字符位置分桶，转成 LIS 问题：
# LCS(a, b) = LIS(把 a 的每个字符替换成它在 b 中的所有下标，逆序排列后拼接)
# 当 b 中字符互不相同时，退化成 O(n log n)
这个转化只在「\(b\) 中元素互不相同」时才把复杂度降到 \(O(n\log n)\)； 一般情况仍是 \(O(nm)\)。
最长公共子串（注意区别）¶
子串要求连续，是另一个模型：
答案 \(= \max f[i][j]\)（不是 \(f[n][m]\)）。
更快的做法是后缀自动机或二分 + 哈希，见 字符串哈希。
4 编辑距离¶
把 \(a\) 变成 \(b\) 的最少操作数（插入 / 删除 / 替换各 1 次代价）：
三个候选分别对应删除 \(a_i\)、插入 \(b_j\)、替换。
| 变式 | 改动 |
|---|---|
| 只允许插入删除 | 去掉 \(f[i-1][j-1]\) 那一项，答案 \(= n + m - 2\cdot\text{LCS}\) |
| 操作代价不同 | 把 1 换成对应代价 |
| 允许相邻交换 | Damerau–Levenshtein，多一个 \(f[i-2][j-2]+1\) 的候选 |
5 数字三角形与坐标 DP¶
从顶点走到底边，每步走左下或右下，求路径和最大：
坐标 DP 是同一族：网格里只能向右/向下走，\(f[i][j] = a[i][j] + \max(f[i-1][j], f[i][j-1])\)。 经典的「过河卒」就是加了障碍的版本。
BISHI135 三角形取数(Hard Version)（中等）¶
数字三角形（居中摆放，第 \(i\) 行有 \(2i-1\) 个数），每步走左下/正下/右下， 限制 \(|\text{左下次数} - \text{右下次数}| \le k\)，求路径和最大。\(n \le 300\)。
这题最大的价值是它示范了「换坐标系消掉一维状态」。
朴素想法：把 \((l - r)\) 当成 DP 的第三维，\(O(n^3) = 2.7\times10^7\)。能过，但完全没必要。
观察：给每个数一个「绝对列号」\(c\)。第 \(i\) 行的第 \(j\) 个数（\(j = 1..2i-1\)）的绝对列号是
这样一来：正下方 = \(c\) 不变，左下 = \(c-1\)，右下 = \(c+1\)，起点在 \(c = n\)。于是终点列号满足
约束 \(|l-r| \le k\) 等价于「终点列号落在 \([n-k,\ n+k]\) 内」—— 根本不需要把 \((l-r)\) 当成状态！
剩下就是最朴素的数字三角形 DP：
（下标是「行内序号」，上一行序号比本行小 0/1/2，正好对应右下/正下/左下三种来法。）
坑： 1. 行内序号与绝对列号的换算是本题的全部难点，画个 \(n=3\) 的图对一遍再动手； 2. 边界：上一行的序号必须落在 \([1, 2i-3]\) 内，越界的候选要跳过； 3. \(a_{i,j}\) 可以是 \(-2\times10^9\)，累加 300 行会到 \(-6\times10^{11}\)，C++ 必须
long long（Python 无此虑）； 4. 答案只在最后一行的合法列号范围内取最大值，不是全局最大。方法论：看到「两个计数之差有界」这类约束，先问一句—— 换个坐标系能不能把它变成「位置的范围约束」？ 能的话就省掉一整维状态。这比硬加一维再优化划算得多。
题解：solutions/nowcoder/BISHI135/sol.py（已通过官方样例验证）
6 Python 下的规模判据¶
线性 DP 的状态数直接决定可行性：
| 状态数 | Python 现实性 | 应对 |
|---|---|---|
| \(\le 10^6\) | ✅ 安全 | 直接写 |
| \(10^6 \sim 10^7\) | ⚠️ 必须把内层下沉 C 层 | map / 切片 / accumulate |
| \(\ge 10^7\) | ❌ 基本无望 | 换算法降维，或接受 TLE 并标注 |
降维的常见手段：
| 手段 | 例子 |
|---|---|
| 换坐标系消掉一维 | BISHI135 |
| 用数据结构维护转移的最优值 | 单调队列、树状数组（见DP 优化） |
| 发现状态间的单调性 | 决策单调性（见DP 优化） |
| 用组合数学替代 DP | BISHI72 用 0/1 转化 + 组合计数替代分治 |
7 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI133 | 最长不下降子序列 | 简单 | 题解 |
| BISHI134 | 最大子段和 | 简单 | 题解 |
| BISHI135 | 三角形取数(Hard Version) | 中等 | 题解 |
| BM65 | 最长公共子序列(二) | 中等 | 题解 |
| BM66 | 最长公共子串 | 中等 | 题解 |
| BM67 | 不同路径的数目(一) | 简单 | 题解 |
| BM68 | 矩阵的最小路径和 | 中等 | 题解 |
| BM69 | 把数字翻译成字符串 | 中等 | 题解 |
| BM71 | 最长上升子序列(一) | 中等 | 题解 |
| BM72 | 连续子数组的最大和 | 简单 | 题解 |
| BM75 | 编辑距离(一) | 较难 | 题解 |
| BM76 | 正则表达式匹配 | 较难 | 题解 |
| BM78 | 打家劫舍(一) | 中等 | 题解 |
| BM79 | 打家劫舍(二) | 中等 | 题解 |
| BM80 | 买卖股票的最好时机(一) | 简单 | 题解 |
| BM81 | 买卖股票的最好时机(二) | 中等 | 题解 |
| BM82 | 买卖股票的最好时机(三) | 较难 | 题解 |
| LC53 | 最大子数组和 | 中等 | 题解 |
| LC72 | 编辑距离 | 中等 | 题解 |
| LC121 | 买卖股票的最佳时机 | 简单 | 题解 |
| LC152 | 乘积最大子数组 | 中等 | 题解 |
| LC198 | 打家劫舍 | 中等 | 题解 |
| LC300 | 最长递增子序列 | 中等 | 题解 |
| LC1143 | 最长公共子序列 | 中等 | 题解 |
面试题单里的十四道线性 DP 题¶
本章前五节的每个模型，题单里都有对应的题，正好逐节对照。
§1 最大子段和。 连续子数组的最大和就是 Kadane 的原样形态： 维护「以当前位置结尾的最大和」，非正就丢弃重开。 题面要求至少选一个元素，所以初值取 \(a_0\) 而不是 0——这个边界一旦取 0，全负数组会返回 0。
§2 最长上升子序列。 最长上升子序列(一)只要长度，
数据规模允许 \(O(n^2)\) 的朴素写法，但 bisect 那版 \(O(n\log n)\) 代码更短：
维护「长度为 \(k\) 的上升子序列的最小结尾」，新元素用 bisect_left 定位后原地替换。
那个数组本身不是任何一个合法的子序列，只是各长度的最优结尾，这一点 §2 强调过。
§3 最长公共子序列，以及它最容易被混淆的邻居。 最长公共子序列(二)要求输出具体方案，所以不能只滚动一维， 要么保留整张 \(n \times m\) 表回溯，要么另记转移方向。 最长公共子串则是连续版本：转移从「三选一取最大」变成 「字符相同才由左上角加一，不同就归零」，且答案不在 \(f_{n,m}\) 而在全表最大值处。 子序列与子串差一个字，转移方程与取答案的位置都不同，这两题放在一起做最能记住。
§4 编辑距离。 编辑距离(一)是三种操作等代价的标准版，
按 §4 的方程直接写。正则表达式匹配是它的近亲——同样是两个串下标做二维状态，
只是转移由 . 与 * 两个通配符决定。* 那一支要同时考虑「匹配零次」与「多匹配一次」，
写成 \(f_{i,j} = f_{i,j-2} \lor (f_{i-1,j} \land \text{可匹配})\)；
* 与它前面那个字符是一个整体，跳过时要一次跳两格，这是这题最集中的错法。
§5 坐标 DP。 不同路径的数目(一)与矩阵的最小路径和是同一张网格上的两问： 前者求方案数（转移是加法），后者求最小代价（转移是 \(\min\) 再加上本格代价）。 两题都只依赖上一行，按 100.5 滚成一维即可。 BM67 还有一条不用动态规划的路：答案就是组合数 \(\binom{n+m-2}{n-1}\)， 见 组合数学。
没有直接对应小节的五道。
把数字翻译成字符串是「爬楼梯 ＋ 合法性判断」：
\(f_i = f_{i-1}\cdot[\text{单字符合法}] + f_{i-2}\cdot[\text{两字符合法}]\)，
合法性判断里最容易漏的是前导零——06 不能当作 6 来翻译。
打家劫舍(一)是最基本的「选或不选且不能相邻」：\(f_i = \max(f_{i-1},\ f_{i-2} + a_i)\)。 打家劫舍(二)把房子排成环，处理办法是拆成两条链各做一遍： 一条强制不选第一间、一条强制不选最后一间，取较大者。 环形问题拆成若干条链是通用手法，比给状态加一维「首元素选没选」更省事。
买卖股票的最好时机(一)、买卖股票的最好时机(二)、买卖股票的最好时机(三) 是同一族的状态机动态规划，难度阶梯很整齐： BM80 只许交易一次，记住「历史最低价」一趟扫完； BM81 不限次数，每段上涨都可以吃下，等价于把所有正差值相加； BM82 最多两次交易，要开 \(f[i][j][0/1]\) 三维（第 \(i\) 天、已用 \(j\) 次、手上有没有股票）， 按天推进。第三题的状态设计能写对，这一族就都会了—— 状态里必须同时含「已用交易次数」与「持仓与否」，少一维就补不出转移。
另一处题库里的七道线性动态规划题¶
四道对应本章已有的模板节，只记差异。 LC 300. 最长递增子序列就是最长不下降子序列那一节的原题，\(O(n^2)\) 与 \(O(n \log n)\) 两版都在那里； LC 1143. 最长公共子序列对应同名的那一节，两串长度都不超过 \(1000\)，\(O(nm)\) 的二维表直接可行； LC 72. 编辑距离对应编辑距离那一节，三种操作对应三个转移来源， 初始化的那一行与那一列分别是「全删」与「全插」的代价。 LC 121. 买卖股票的最佳时机是 BM80 那一组里的第一问： 只允许做一次交易时连状态机都不用，扫一遍维护「到目前为止的最低价」即可，\(O(n)\)、\(O(1)\) 空间。
LC 53. 最大子数组和与 LC 152. 乘积最大子数组：状态要带几条，取决于运算的符号性质。 LC53 一条就够：\(f_i\) 表示以 \(i\) 结尾的最大子段和， 转移是 \(f_i = \max(a_i,\ f_{i-1} + a_i)\)，答案取所有 \(f_i\) 的最大值，\(O(n)\)。 换成乘积之后一条不够——负负得正，当前的最小值乘上一个负数就成了最大值， 所以 LC152 要同时维护「以 \(i\) 结尾的最大积」与「最小积」两条， 每步用 \(a_i\)、\(\max \cdot a_i\)、\(\min \cdot a_i\) 三者分别取大、取小。 只维护最大值的写法在 \([-2, 3, -4]\) 上会给出 \(3\) 而不是 \(24\)。
LC 198. 打家劫舍：约束要写进状态，不能写进循环。 相邻两间不能同时取，状态取「前 \(i\) 间的最大收益」， 转移是「不取第 \(i\) 间」与「取第 \(i\) 间再加上前 \(i-2\) 间」二者取大， \(O(n)\)、滚动两个变量即可。 把「不能相邻」当成遍历时的临时判断是写不出来的—— 第 \(i\) 间该不该取取决于前面整段的取法，它不是一个局部条件。
8 本章速查¶
| 模型 | 转移 | 关键点 |
|---|---|---|
| 最大子段和 | \(f_i = a_i + \max(f_{i-1}, 0)\) | 非空 ⇒ 初值取 \(a_1\) 不是 0 |
| LIS \(O(n^2)\) | \(f_i = 1 + \max\{f_j\}\) | \(n \le 1000\) 可用 |
| LIS \(O(n\log n)\) | tails + bisect |
严格上升 left、不下降 right |
| LCS | 相等则 \(+1\)，否则取 max | \(O(nm)\)，串行依赖难批处理 |
| 最长公共子串 | 不等则清 0 | 答案是全局 max 不是 \(f[n][m]\) |
| 编辑距离 | 三候选 \(+1\) | 只增删时可由 LCS 推出 |
| 数字三角形 / 坐标 DP | 从上/左转移 | 障碍格设为不可达 |
| 陷阱 | 正解 |
|---|---|
| 最大子段和初值取 0 | 全负数组会输出 0，必须取 \(a_1\) |
| LIS 等号写错 | 不下降用 bisect_right，严格上升用 bisect_left |
拿 tails 当答案序列 |
它只是最优结尾值，不是子序列 |
3.9 用 bisect(key=) |
不支持，预先构造键数组 |
| 「两计数之差有界」硬加一维 | 先试换坐标系（BISHI135） |