第 102 章　线性 DP¶

配套例题：BISHI133 最长不下降子序列、BISHI134 最大子段和、BISHI135 三角形取数(Hard Version) 来源：S3 day6/DP入门.md（LIS 及其优化）、S4 模板.docx（LIS \(n\log n\)、最长公共子串）

「线性 DP」指状态沿一个（或两个）序列维度推进的 DP。它是笔试出现最多的 DP 形态，四个经典模型：最大子段和、LIS、LCS、编辑距离。

102.1　最大子段和（Kadane）¶

选一个非空连续子数组使元素和最大。

设 \(f_i\) = 「以 \(i\) 结尾」的最大子段和。枚举最后一步：这一段要么把前面接上，要么从 \(i\) 重开。

\[f_i = a_i + \max(f_{i-1},\ 0)\]

答案 \(= \max_i f_i\)。

等价视角：前缀和¶

\[\text{答案} = \max_i \Big(S_i - \min_{j < i} S_j\Big)\]

一边扫一边记录历史最小前缀和。两种写法完全等价，前缀和视角在带长度限制 （如「长度不超过 \(k\) 的最大子段和」）时更容易扩展成单调队列，见 104-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/BISHI134.py（已通过官方样例验证）

102.2　最长上升子序列（LIS）¶

\(O(n^2)\) 朴素 DP¶

\(f_i\) = 以 \(i\) 结尾的最长上升子序列长度：

\[f_i = 1 + \max\{f_j \mid j < i,\ a_j < a_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/BISHI133.py（已通过官方样例验证）

与 Dilworth 定理的联系¶

「最少用几个不上升子序列覆盖整个序列」的答案等于「最长上升子序列的长度」。这是 Dilworth 定理的直接推论，也是 NOIP 导弹拦截问题的第二问。证明见 111-偏序集与Dilworth定理。

102.3　最长公共子序列（LCS）¶

两个序列 \(a\)（长 \(n\)）、\(b\)（长 \(m\)）：

\[ f[i][j] = \begin{cases} f[i-1][j-1] + 1 & a_i = b_j \\ \max(f[i-1][j],\ f[i][j-1]) & a_i \ne b_j \end{cases} \]

\(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)\)。

最长公共子串（注意区别）¶

子串要求连续，是另一个模型：

\[ f[i][j] = \begin{cases} f[i-1][j-1] + 1 & a_i = b_j \\ 0 & a_i \ne b_j \end{cases} \]

答案 \(= \max f[i][j]\)（不是 \(f[n][m]\)）。

更快的做法是后缀自动机或二分 + 哈希，见 36-哈希与字符串哈希。

102.4　编辑距离¶

把 \(a\) 变成 \(b\) 的最少操作数（插入 / 删除 / 替换各 1 次代价）：

\[ f[i][j] = \begin{cases} j & i = 0 \\ i & j = 0 \\ f[i-1][j-1] & a_i = b_j \\ 1 + \min\big(f[i-1][j],\ f[i][j-1],\ f[i-1][j-1]\big) & \text{否则} \end{cases} \]

三个候选分别对应删除 \(a_i\)、插入 \(b_j\)、替换。

变式	改动
只允许插入删除	去掉 \(f[i-1][j-1]\) 那一项，答案 \(= n + m - 2\cdot\text{LCS}\)
操作代价不同	把 1 换成对应代价
允许相邻交换	Damerau–Levenshtein，多一个 \(f[i-2][j-2]+1\) 的候选

102.5　数字三角形与坐标 DP¶

从顶点走到底边，每步走左下或右下，求路径和最大：

\[f[i][j] = a[i][j] + \max\big(f[i-1][j-1],\ f[i-1][j]\big)\]

坐标 DP 是同一族：网格里只能向右/向下走，\(f[i][j] = a[i][j] + \max(f[i-1][j], f[i][j-1])\)。 S3 课件《DP 入门》的「过河卒」就是加了障碍的版本。

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 = j + (n - i)\]

这样一来：正下方 = \(c\) 不变，左下 = \(c-1\)，右下 = \(c+1\)，起点在 \(c = n\)。于是终点列号满足

\[c_{\text{end}} = n + (r - l) \quad\Longrightarrow\quad l - r = n - c_{\text{end}}\]

约束 \(|l-r| \le k\) 等价于「终点列号落在 \([n-k,\ n+k]\) 内」—— 根本不需要把 \((l-r)\) 当成状态！

剩下就是最朴素的数字三角形 DP：

\[f[i][j] = a[i][j] + \max\big(f[i-1][j-2],\ f[i-1][j-1],\ f[i-1][j]\big)\]

（下标是「行内序号」，上一行序号比本行小 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/BISHI135.py（已通过官方样例验证）

102.6　Python 下的规模判据¶

线性 DP 的状态数直接决定可行性：

状态数	Python 现实性	应对
\(\le 10^6\)	✅ 安全	直接写
\(10^6 \sim 10^7\)	⚠️ 必须把内层下沉 C 层	`map` / 切片 / `accumulate`
\(\ge 10^7\)	❌ 基本无望	换算法降维，或接受 TLE 并标注

降维的常见手段：

手段	例子
换坐标系消掉一维	BISHI135
用数据结构维护转移的最优值	单调队列、树状数组（见 104 章）
发现状态间的单调性	决策单调性（见 104 章）
用组合数学替代 DP	BISHI72 用 0/1 转化 + 组合计数替代分治

102.7　本章速查¶

模型	转移	关键点
最大子段和	\(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）

第 102 章 线性 DP¶

102.1 最大子段和（Kadane）¶