线性 DP 入门

依旧感谢 Claude 老师

最长上升子序列

题意

给定长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

N ≤ 1000，元素范围 1e-9 ~ 1e9。输入例：3 1 2 1 8 5 6 → 输出 4（1 2 5 6 或 1 2 4 ?……最长是 4）。

朴素 O(N²) 思路

状态：f[i] = 以第 i 个数结尾的最长上升子序列长度。

转移：往前扫所有 j < i，如果 w[i] > w[j] 就可以接在 f[j] 后面：

f[i] = max(f[i], f[j] + 1)    // 0 <= j < i，且 w[i] > w[j]

找不到比自己小的数时 f[i] = 1（单独成一段）。

答案：所有 f[i] 的最大值，不是 f[N]。

#include <iostream>
using namespace std;
const int N = 100010;
int n, w[N], f[N];
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];

    int mx = 1;
    for(int i = 0; i < n; i++){
        f[i] = 1;
        for(int j = 0; j < i; j++){
            if(w[i] > w[j]) f[i] = max(f[i], f[j] + 1);
        }
        mx = max(mx, f[i]);
    }
    cout << mx;
    return 0;
}

复杂度：O(N²)，N = 1e5 就超时了。

重点：nlogn 优化——为什么 tails 不是 LIS，却能正确统计长度

优化动机

朴素的 O(N²) 卡在第二层：每次都要回头扫所有 f[j]。能不能让"找一个能接上的最长前缀"变成 O(log N)？

tails 数组的含义

tails[k] = 长度为 k+1 的上升子序列里，末尾元素的最小值

关键观察：为了让序列后面"更容易"接上新数，每个长度档位的末尾都希望尽量小。所以 tails 数组天然是严格单调递增的——长度更大的子序列末尾一定更大。

替换规则

遍历原数列 w[i]：

#include <iostream>
using namespace std;
const int N = 100010;
int n, cnt;
int w[N], tails[N];

// 二分：找 tails 中第一个 >= x 的下标
int find(int x){
    int l = 0, r = cnt - 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(tails[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];

    tails[cnt++] = w[0]; // 第一个数
    for(int i = 1; i < n; i++){
        if(w[i] > tails[cnt - 1]){
            tails[cnt++] = w[i]; // 接上去
        }else{
            int pos = find(w[i]); // 二分找替换位置
            tails[pos] = w[i];
        }
    }
    cout << cnt;
    return 0;
}

重点：为什么 tails 数组本身不是 LIS，却能正确给出 LIS 长度

先给一个巧合情况：1 5 6 2 8

朴素 LIS 长度 = 4（1 5 6 8，长度 4）。

跑一遍 nlogn，得到的 tails 数组变化：

处理 w[i] 操作 tails 数组 cnt
1 第一个数 [1] 1
5 5 > 1 [1, 5] 2
6 6 > 5 [1, 5, 6] 3
2 2 在 [1,5,6] 里找 >=2 的位置（pos=1），替换 [1, 2, 6] 3
8 8 > 6 [1, 2, 6, 8] 4

最终 tails = [1, 2, 6, 8]，刚好是原数列的一个 LIS，长度 4 ✓

再给一个反例：试 4 2 3 1 5：

朴素 LIS：2 3 5，长度 3。

跑 nlogn：

处理 w[i] 操作 tails 数组 cnt
4 第一个 [4] 1
2 替换 pos=0 [2] 1
3 接上去 [2, 3] 2
1 替换 pos=0 [1, 3] 2
5 接上去 [1, 3, 5] 3

tails = [1, 3, 5]，它本身不是原数列的子序列（1 在最末尾、3 在中间、5 在最末尾）。但 cnt=3 是正确的 LIS 长度 ✓

这就是关键：tails 数组可能根本不是一个合法的子序列，但 cnt 始终等于 LIS 长度。

严格论证（核心）

引理 1：tails 数组严格单调递增
tails[0] < tails[1] < tails[2] < ...

反证：假设更新后出现了 tails[i] >= tails[i+1]，看图：

长度 i+1 的子序列末尾：tails[i]
长度 i+2 的子序列末尾：tails[i+1]  <= tails[i]

长度 i+2 的子序列把前面 i+1 个拿出来，就是一个长度 i+1 的上升子序列，末尾是 tails[i+1]。但 tails[i+1] <= tails[i]，于是存在一个长度 i+1 的上升子序列，末尾比 tails[i] 还小。

这违反 tails[i] 是"长度 i+1 末尾最小值"的定义。矛盾，所以 tails 必须严格递增。

严格递增很关键——这是后面二分能用的前提。

引理 2：每次更新要么让 cnt +1，要么不动 cnt，且不破坏已有的 LIS 长度

假设处理完 w[0..i-1] 后 cnt = LIS([w[0..i-1]])，现在处理 w[i]。分两种情况：

情况 A：w[i] > tails[cnt-1]

tails[cnt-1] 是当前所有长度 cnt 的子序列末尾的最小值。

取一个长度 cnt 的子序列，把 w[i] 接在它后面：因为 w[i] > tails[cnt-1] >= 该子序列末尾，新序列还是上升的，长度变成 cnt+1。

所以新 LIS 长度 ≥ cnt+1。

同时 cnt+1 也是上界——因为任何长度 cnt+2 的上升子序列，必然以某个 w[j]（j <= i）结尾，不可能跳过 w[i] 直接多出长度。所以新 LIS 长度 ≤ cnt+1。

因此新 LIS 长度正好等于 cnt+1，操作就是 tails[cnt++] = w[i]。

情况 B：w[i] <= tails[cnt-1]

w[i] 接不到任何长度 cnt 的子序列后面，所以新 LIS 长度不可能超过 cnt。

关键问题：会不会因为插入了 w[i]，反而让原本存在的长度 cnt 的子序列消失了？

不会。原因是替换不动长度，只动大小。

在 tails 里二分找位置 pos，满足：

tails[pos-1] < w[i] <= tails[pos]    （pos = 0 时左边视为 -∞）

把 tails[pos] 换成 w[i]。换完意味着：

  • 长度 pos+1 的子序列：末尾从 tails[pos] 换成了 w[i]，由于 w[i] < tails[pos]，这条子序列还能存在（甚至末尾更小了，将来更好接数）。
  • 其他长度的子序列：tails 数组的其它位置完全没动，对应的子序列一条都没消失。

所以替换之后，所有长度 k+1（k ≠ pos）的子序列都还在；长度 pos+1 的子序列还能造出来。

推论：新 LIS 长度 = 旧 LIS 长度 = cnt。cnt 不动。

引理 3：cnt 单调不减

每次处理一个新数，要么情况 A 让 cnt +1，要么情况 B 让 cnt 不变。从不减小。

结论

cnt 从 1 开始（处理完第一个数后），每一步要么 +1 要么不变，最终处理完全部 N 个数后 cnt 就是 LIS 长度。

cnt 不会"假增"（情况 A 已经论证了 +1 是真实的新 LIS 长度）； cnt 不会"假稳"（情况 B 论证了替换不破坏已有结构）； 所以 cnt = LIS 长度。证毕。

课件反例：1 5 6 2 8 的"贪心"动机

课件问：**1 3 5 10 6 8**，看到 6 后应该把 1 3 5 10 这条线替换成 1 3 5 6 吗？

答案：必须替换。

保留 1 3 5 10 的代价：6 接不进去（10 > 6），cnt 仍是 3（1 3 5 10），后面 8 接不进去（10 > 8）。cnt = 3。

替换为 1 3 5 6 的好处：6 可以接在 1 3 5 后面，cnt 仍是 3（1 3 5 6），但**6 < 10**，所以 8 可以接上，最终 1 3 5 6 8 长度 4。

留下的尾巴越小，越容易接后面的数——这就是"贪心 + 替换"的核心。

易错点

最长公共子序列 LCS

题意

给定两个长度分别为 N、M 的字符串 A、B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

N, M ≤ 1000，字符均为小写字母。

状态定义

dp[i][j] = A[1..i] 和 B[1..j] 的最长公共子序列长度

转移

分两类：

dp[i][j] = dp[i-1][j-1] + 1

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

不需要单独列 dp[i-1][j-1]。直观上看，dp[i-1][j-1] 是 dp[i-1][j] 和 dp[i][j-1] 都包含的情况，max 自然覆盖。

完整转移

if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1;
else             dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

初始值

dp[0][j] = 0，dp[i][0] = 0（空串和任何串的 LCS = 0）。

代码

#include <iostream>
using namespace std;
const int N = 1010;
int dp[N][N];
char a[N], b[N];
int main(){
    int n, m;
    cin >> n >> m;
    cin >> a + 1 >> b + 1; // 从下标 1 开始存

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else             dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[n][m];
    return 0;
}

易错点

最短编辑距离

题意

给定两个字符串 A、B，把 A 变成 B，可以做三种操作：

  1. 删除：删 A 中某个字符
  2. 插入：在 A 中某个位置插入某个字符
  3. 替换：把 A 中某个字符替换为另一个字符

每种操作代价 1。问把 A 变成 B 最少要多少步。

1 ≤ n, m ≤ 1000。字符均为大写字母。

状态定义

dp[i][j] = 把 A[1..i] 变成 B[1..j] 的最少操作次数

重点：三种操作的"方向"含义

从状态 (i, j) 看前一个状态：

dp[i][j] = dp[i-1][j-1]

完整转移

if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1];
else             dp[i][j] = min({
                                 dp[i-1][j-1] + 1,  // 替换
                                 dp[i-1][j]   + 1,  // 删除
                                 dp[i][j-1]   + 1   // 插入
                             });

重点：初始值

这两个边界是正确性的关键——漏写就会出现 dp[i][0] 默认是 0、然后 min 出来全 0 的灾难。

代码

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int dp[N][N];

int main(){
    cin >> n >> a + 1 >> m >> b + 1;

    // 初始值
    for(int i = 0; i <= n; i++) dp[i][0] = i; // A 删完
    for(int j = 0; j <= m; j++) dp[0][j] = j; // A 插成 B

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1); // 删 / 插
            if(a[i] == b[j]){
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]);     // 跳过
            }else{
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1); // 替换
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

例子：rad → apple

操作序列：删 r → ad，替 d → p → ap，插 p → app，插 l → appl，插 e → apple。共 5 步。

注意：这里没有"先删再加"得到 aple 的方案，因为最少操作下我们走的是"先删 r、再替 d、再插 pplle"这种分解方式。具体走哪条路不影响 dp[3][5] = 5 这个答案。

易错点

易错点汇总

  1. LIS nlogn 中 cnt 的含义：是当前已知 LIS 长度，tails 本身不可还原 LIS 序列。
  2. LIS nlogn 二分用 >=：找第一个 >= x 的位置，保证相同的数也能正确替换。
  3. LCS 字符串下标：从 1 开始存，否则 dp[i-1][j-1] 越界。
  4. 编辑距离初始值：必须写 dp[0][j] = j、dp[i][0] = i。
  5. 编辑距离 A[i] == B[j]：跳过不消耗，dp[i][j] = dp[i-1][j-1]，不是 +1。
  6. 编辑距离三种操作的方向：删 A[i] → dp[i-1][j]，插 B[j] → dp[i][j-1]，替换 → dp[i-1][j-1]。

复杂度对比

题型 朴素 优化
LIS O(n²) O(n log n)（tails + 二分）
LCS O(nm) —
编辑距离 O(nm) —