很多同学学 DP 的第一道坎，是 LCS（最长公共子序列）。
但真正有价值的不是“LCS 本身”，而是它背后那套双序列匹配的思维模型。

你会发现：
点积最大、编辑距离、加权匹配、序列对齐、甚至一些“分段配对”的题……本质都在干同一件事：

在两条序列里，按顺序挑一些位置配对（或者不配对），让总收益最大 / 总代价最小。

这篇文章就用 LCS 当起点，把双序列匹配 DP 的经典做法一次讲清。

---

双序列 DP 的“骨架”长什么样？

几乎所有双序列 DP，都绕不开一个二维状态：

$$dp[i][j]$$

它通常表示：

只看 $A[1..i]$ 和 $B[1..j]$，在某种规则下能得到的最优值。

然后转移基本来自三个方向：

• 上：dp[i-1][j]（不使用 $A[i]$）

• 左：dp[i][j-1]（不使用 $B[j]$）

• 左上：dp[i-1][j-1]（同时用 $A[i]$ 和 $B[j]$，形成一对匹配）

你可以把它想成一张网格：
从 $(0,0)$ 走到$(n,m)$，每一步要么向下、向右（跳过元素），要么斜着走（匹配一对）。

这就是 LCS 的“网格路径模型”，也是双序列 DP 的母体,也可以认为是网格图DP的经典模型变体。

---

LCS

LCS 的规则很简单：只有当 A[i]==B[j] 才能匹配。

状态：
dp[i][j] = $A[1\dots i], B[1 \dots j]$的 LCS 长度

转移：

• 若 A[i]==B[j]

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

• 否则

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

这道题你学会后，下一步就是：把“匹配条件”从“相等”升级成“有收益/有代价”。

---

加权 LCS

很多题不是问“匹配多少个”，而是问：

匹配 $(i,j)$ 这对值多少分？

比如：
匹配一对给分 $w(i,j)$，不匹配就不加分。

状态：
dp[i][j] = 最大总得分

转移：

$$dp[i][j]=\max\Big( dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]+w(i,j) \Big) $$

你可以把它理解成：
LCS 的 +1 只是 w(i,j)=1 的特例。

参考题目

最大绝对差和子序列

题目描述

两个整数数组 $A$ 和 $B$，长度分别为 $N$ 和 $M$。

需要从 $A$ 中选择一个子序列，并从 $B$ 中选择一个长度相同的子序列。

假设从 $A$ 中选出的子序列为 $A' = \{a'_1, a'_2, \dots, a'_k\}$，从 $B$ 中选出的子序列为 $B' = \{b'_1, b'_2, \dots, b'_k\}$（其中 $k \ge 1$）。

根据子序列的定义，这些元素必须保持在原数组中的相对顺序。即存在下标 $1 \le i_1 < i_2 < \dots < i_k \le N$ 和 $1 \le j_1 < j_2 < \dots < j_k \le M$，使得 $a'_p = A_{i_p}$ 且 $b'_p = B_{j_p}$。

定义这对子序列的绝对差和为对应位置元素差值的绝对值之和：

$$S = \sum_{p=1}^{k} |a'_p - b'_p|$$

请你计算并输出所有可能的非空子序列对中，能够获得的最大绝对差和。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示数组 $A$ 和 $B$ 的长度。

第二行包含 $N$ 个整数，表示数组 $A$ 的元素。

第三行包含 $M$ 个整数，表示数组 $B$ 的元素。

输出格式

输出一个整数，表示最大的绝对差和。

样例输入 #1

3 3
1 3 5
2 4 6

样例输出 #1

6

样例输入 #2

2 2
1 2
3 4

样例输出 #2

4

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N, M \le 500$
• 数组中的数值在 $[-1000, 100]$ 范围内。

---

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 505;
int a[N], b[N], dp[N][N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int j = 1; j <= m; j++) cin >> b[j];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + llabs(a[i] - b[j]));
		}
	}

	cout << dp[n][m];
	return 0;
}

编辑距离

编辑距离是双序列 DP 的另一条主线：
不是求最大得分，而是求最小代价。

状态：
dp[i][j] = A[1..i] 变成 B[1..j] 的最小代价

转移：

• 删除 $A[i]$：dp[i-1][j] + del

• 插入 $B[j]$：dp[i][j-1] + ins

• 替换/匹配：dp[i-1][j-1] + cost(A[i],B[j])

这类题的网格图像更明显：
上、左、左上三种操作，像走迷宫一样。

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

$A, B$ 均只包含小写字母。

输入格式

第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A, B$ 的长度均小于 $2000$。

输出格式

只有一个正整数，为最少字符操作次数。

输入 #1

sfdqxbw
gfdgw

输出 #1

4

说明/提示

对于 $100 \%$ 的数据，$1 \le |A|, |B| \le 2000$。

参考代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2005;
int dp[N][N];

signed main() {
	string s, t;
	cin >> s >> t;
	int n = (int)s.size(), m = (int)t.size();
	s = " " + s;
	t = " " + t;

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0) { dp[i][j] = j; continue; }
			if (j == 0) { dp[i][j] = i; continue; }
			if (s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
			else dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
		}
	}

	cout << dp[n][m];
	return 0;
}

---

最大点积

很多同学写双序列 DP 写到这里会翻车：
因为题目要求两个子序列都必须非空。

给定两个整数数组 $A$ 与 $B$。你需要分别从 $A$ 与 $B$ 中选出两个长度相同且非空的子序列 $A'$ 与 $B'$，使它们的点积最大。

子序列的定义：从原数组中删除若干元素（可以不删），剩余元素按原有相对顺序组成的新序列。

点积定义：设

$$A' = [a_1,a_2,\dots,a_k],\quad B' = [b_1,b_2,\dots,b_k] $$

则

$$A'\cdot B'=\sum_{i=1}^{k} a_i b_i$$

请输出最大可能的点积值。

点积的本质就是加权匹配：
匹配 (i,j) 的收益是 $A_i\cdot B_j$。

但如果你直接套加权 LCS，会出现一个坑：

• 空匹配的值如果默认为 0

• 当全是负数时，答案会被“0”污染（错误）

所以这题必须用 -INF 初始化，并显式允许“从这一对开始”。

正确转移（精华）是：

$$dp[i][j]=\max\Big( dp[i-1][j],\ dp[i][j-1],\ A_iB_j+\max(0,dp[i-1][j-1]) \Big) $$

理解这句就够了：

• $A_iB_j$：我就选这一对当起点（保证非空）

• $dp[i-1][j-1] + A_iB_j$：接在之前的匹配后面

• 再和 “跳过” 取最大

这就是“非空匹配”的标准补丁：+ max(0, dp[i-1][j-1])

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

    const ll neg = -(1LL << 60);
    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, neg));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ll p = 1LL * a[i] * b[j];
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            dp[i][j] = max(dp[i][j], p);
            if (dp[i - 1][j - 1] > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + p);
            else dp[i][j] = max(dp[i][j], p);
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}

LCIS

很多同学学完 LCS 之后，会遇到这种题：

求两个序列的最长公共递增子序列长度（或最大权值）

它看起来像 “LCS + LIS”，但直接三维搞会爆。
真正的经典做法是 $O(n \cdot m)$，精髓是：

外层枚举$A[i]$，内层扫 $B[j]$，维护一个 $best$。

参考题目：POJ:2127

题目描述

给定两个整数序列 $A$ 与 $B$。

我们称序列 $S=(S_1,S_2,\dots,S_L)$ 是序列 $A=(A_1,A_2,\dots,A_N)$ 的一个递增子序列，当且仅当存在下标

$$1 \le i_1 < i_2 < \cdots < i_L \le N$$

使得对所有 $1 \le t \le L$，都有 $S_t = A_{i_t}$，并且满足严格递增：

$$S_1 < S_2 < \cdots < S_L.$$

现在你需要在两个序列 $A$ 与 $B$ 中各取一个子序列，使它们完全相同且严格递增，并使其长度最大。请输出该最大长度以及任意一个满足条件的序列。

输入格式

输入包含两段序列描述：

• 第一行一个整数 $N$，表示序列 $A$ 的长度。

• 第二行 $N$ 个整数 $A_1,A_2,\dots,A_N$。

• 第三行一个整数 $M$，表示序列 $B$ 的长度。

• 第四行 $M$ 个整数 $B_1,B_2,\dots,B_M$。

输出格式

• 第一行输出一个整数 $L$，表示 $A$ 与 $B$ 的最大公共递增子序列（LCIS）的长度。

• 第二行输出该子序列本身（共 $L$ 个整数，按递增顺序输出）。
  若存在多种答案，输出任意一种即可。

样例输入

5
1 4 2 5 -12
4
-12 1 2 4

样例输出

2
1 4

数据范围与约定

• $1 \le N,M \le 500$

• $-2^{31} \le A_i, B_i < 2^{31}$

1）状态直觉

当我们把 A[i] 当成“结尾”，想匹配到 B[j] 作为结尾时：

• 必须 A[i] == B[j]

• 之前匹配的数必须 < A[i]，并且在 B 的位置 < j

所以我们在扫 B 的过程中维护：

$$best = \max\{ dp[j'] \mid B[j'] < A[i],\ j'<j \}$$

一旦遇到 B[j] == A[i]，就能更新：

$$dp[j] = \max(dp[j], best + 1)$$

这里 dp[j] 表示：以 B[j] 结尾的 LCIS 长度。

2）核心流程

• 初始化 dp[1..m]=0

• 对每个 i=1..n：

  • best=0

  • 扫 j=1..m：

    • 若 B[j] < A[i]：best=max(best, dp[j])

    • 若 B[j] == A[i]：dp[j]=max(dp[j], best+1)

复杂度 O(nm)，没有三维。

这题最大的价值：它告诉你“双序列 DP 不一定非得 dp[i][j]”，有时把一维放在 B 上，外层扫 A 反而更强。

---

参看代码:

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 505;
int a[N], b[N], dp[N], pre[N], ans[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int j = 1; j <= m; j++) cin >> b[j];
	
	for (int i = 1; i <= n; i++) {
		int cur = 0, pos = 0;
		for (int j = 1; j <= m; j++) {
			if (b[j] < a[i] && dp[j] > cur) {
				cur = dp[j];
				pos = j;
			}
			if (b[j] == a[i] && cur + 1 > dp[j]) {
				dp[j] = cur + 1;
				pre[j] = pos;
			}
		}
	}
	
	int len = 0, ed = 0;
	for (int j = 1; j <= m; j++) {
		if (dp[j] > len) {
			len = dp[j];
			ed = j;
		}
	}
	
	int top = 0;
	while (ed) {
		ans[++top] = b[ed];
		ed = pre[ed];
	}
	
	cout << len << "\n";
	for (int i = top; i >= 1; i--) {
		cout << ans[i] << (i == 1 ? '\n' : ' ');
	}
	if (len == 0) cout << "\n";
	return 0;
}

加匹配数量

这种题特别常见：
比如“从两序列中选相同长度子序列，长度必须为 k，最大化收益”。

这类题最直观的就是加一维：

$$dp[i][j][t]$$

表示只看前$i$、前$j$，匹配了 $t$ 对的最优值。

转移仍然是 LCS 的三方向：

• 跳过$A[i]$：dp[i-1][j][t]
• 跳过$B[j]$：dp[i][j-1][t]
• 匹配$(i,j)$：dp[i-1][j-1][t-1] + w(i,j)（满足条件才允许）

当然也可以转化成 网格图上的模型，就是把这个问题 转化成旧的模型,相当于左上到右下的 最优花费，但是限定右下只能用K次，每次决策可以

• 向右
• 向下
• 向右下

优化：把 $i$ 维滚掉

如果 $n,m$ 只有几百，三维也能写。
但一旦 $n,m$大一点，就必须滚动（甚至用 t 做外层）。

写题时你只记住一句话：

“固定匹配数” = “LCS 的 dp[i][j] 再加一维 t”

---

冷却窗口 / 间隔限制

这种题通常长这样：

• 选出若干对匹配 $(i,j)$

• 但要求$i$ 之间至少相差 L（或者 j 也有限制）

• 或者“选了 $A[i]$，下一次必须从$i+L$ 之后开始”

这时你会发现：
普通 dp[i-1][j-1] 不够用了，因为你不能从任意前一个位置转移过来。

经典处理方式：把“可转移范围”变成“前缀最值”

假设限制是：下一次匹配必须满足 i' >= i + L，对 B 也类似。

那么当我们在计算 (i,j) 时，需要的其实是：

$$\max dp[i-L][j-1] \quad 或 \quad \max dp[\le i-L][\le j-1] $$

这类“范围最大值”通常有两种手段：

1）前缀最大值数组：
pre[i][j] = max(dp[0..i][0..j])
然后查询范围变成 O(1)。

2）维护窗口最大值（更像滑动窗口）：
当 i 增长时，让某些状态进入/离开可用集合，用 deque / 线段树维护最大值。

你不用一上来就写线段树，很多题只要前缀最大值就够：

• 转移需要 max(dp[x][y]) 的矩形区域
  → 直接 pre 一下就行

冷却题的核心不是 DP 难，而是“把限制转化成可快速查询的最大值”。

---

分段配对

常见变形就是

A 划成 m 段，第 j 段段和乘 b[j]，最大化总和。

它的正统 DP 是：

$$dp[i][j]=\max_{p< i}\big(dp[p][j-1] + b_j\cdot(s[i]-s[p])\big) $$

其中 s[i] 是前缀和。

考虑元素 $a_i$ 放到哪：

1）$a_i$ 单独成一段（新开第 $j$ 段）

前 $i-1$ 个必须已经做完 $j-1$ 段：

$$dp[i][j] \leftarrow dp[i-1][j-1] + b_j \cdot a_i$$

2）$a_i$ 加到最后一段（延长第 $j$ 段）

前 $i-1$ 个已经做完 $j$ 段，现在把 $a_i$ 加进第 $j$ 段，段和增加 $a_i$，收益就增加 $b_j\cdot a_i$：

$$dp[i][j] \leftarrow dp[i-1][j] + b_j \cdot a_i$$

于是合并成一句非常“LCS味”的式子：

$$\boxed{dp[i][j] = \max\big(dp[i-1][j],\ dp[i-1][j-1]\big) + b_j \cdot a_i} $$

复杂度$O(n \times m)$

---

一张总结表

类型	一句话特征	核心状态/技巧
加权LCS	转移代价	可以看作转移时，状态节点之间转移的边权不为1
删点集合	序列非空	允许从任意起点开始，需要注意转移时候决策
LCIS	公共 + 递增	外层枚 A，内层扫 B，维护 best
固定匹配数	特殊转移有次数限制或者匹配某一对有顺序次数的依赖	加一维度，dp[i][j][t] 三维，滚动优化
冷却/间隔	匹配后必须隔 L	把可转移区变成前缀/窗口最大值

---

最后一句：你要培养的“肌肉”是什么？

你刷双序列题，练的不是某个题，而是常见的转化能力，从新问题，经过转化分析，转成旧模型的能力：

1. 识别“上/左/左上”骨架（能跳过吗？能配对吗？）
2. 发现限制导致的“范围转移”（矩形 max、窗口 max）
3. 拆 cost 结构做优化（把枚举 p 变成维护最值）

现实中，往往大多数人不擅长总结，当然你如果天赋异禀，你确实在任何时候是可以现推，但是往往绝大多数人之间不同的地方在于，有的擅长总结和发散考点，而有的人不擅长或者从来不总结复盘，而往往很多出题人只是在某一个经典老题的基础上进行加入一些限制的idea，导致就会出现大多数人无从下手，而复盘总结分析，发散是我们平时就要训练的事，这能够让你在下一次或者之后遇到类似的思维，你能一眼看出出题人的意图和背后的原理，透过现象看本质；