双序列型DP入门

双序列 DP

算法简介

• 时间复杂度：通常为 $O(N \times M)$
• 基本枚举顺序：双层嵌套循环，外层枚举 $A$ 的下标 $i$，内层枚举 $B$ 的下标 $j$。

------



一、LCS 最大匹配模型





1. 核心原理



这是最基础的模型，侧重于找共性。特点是字符不要求连续，只要求相对顺序一致。

• 状态转移：

当考虑 $A[i]$ 和 $B[j]$ 时：

- 若相等，则贡献来源于左上角（延续匹配）。
- 若不等，则贡献来源于左方或上方（继承历史最优）。

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } A[i] == B[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{if } A[i] \neq B[j] \end{cases}$$

------



2. 常用技巧



• 路径输出

记录转移来源（或在填表后逆向倒推）：若 $A[i]==B[j]$ 则向左上走，否则向 $dp$ 值较大的方向走。

• 空间优化

由于 $dp[i]$ 只依赖于 $dp[i-1]$，可利用滚动数组将空间优化至 $O(\min(N, M))$。

• 方案计数

若题目求“有多少种匹配方案”，将 max 改为 sum，且 $A[i] \ne B[j]$ 时通常只继承 $dp[i-1][j]$（取决于题目定义的删除规则）。

------



3. 代码模板





// LCS 通用模板
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (A[i] == B[j]) {
            // 匹配成功：长度加 1
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            // 匹配失败：谁大听谁的
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}



------



二、编辑距离最小代价模型





1. 核心原理



这类问题侧重于做变换。通过增、删、改三种操作将 $A$ 变成 $B$，求最小代价。

• 状态定义：$dp[i][j]$ 为将 $A[1 \dots i]$ 变为 $B[1 \dots j]$ 的最小代价。
• 状态转移：

$$dp[i][j] = \min \begin{cases} dp[i-1][j] + \text{DelCost} \\ dp[i][j-1] + \text{InsCost} \\ dp[i-1][j-1] + (A[i]==B[j] ? 0 : \text{RepCost}) \end{cases}$$

------



2. 常用技巧



• 边界初始化

这是与 LCS 最大的不同点。

$dp[i][0] = i \times \text{DelCost}$ （把 $A$ 删光）

$dp[0][j] = j \times \text{InsCost}$ （从空串插入出 $B$）

• 权值变化

题目可能规定删除 'a' 的代价是 100，删除 'b' 是 200（如 ASCII 删除和），此时 Cost 需动态计算。

------



3. 代码模板





// 最小编辑距离模板
// 1. 初始化边界
for (int i = 1; i <= n; i++) dp[i][0] = i; 
for (int j = 1; j <= m; j++) dp[0][j] = j; 

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]; // 无代价
        } else {
            // 决策：删、增、替 中取最小
            dp[i][j] = min({
                dp[i-1][j] + 1,    // 删除
                dp[i][j-1] + 1,    // 插入
                dp[i-1][j-1] + 1   // 替换
            });
        }
    }
}



------



三、连续子串模型





1. 核心原理



这类问题的核心是连贯性。与 LCS 的区别在于：一旦当前字符不匹配，之前的积累必须清零。

• 状态定义：$dp[i][j]$ 表示以 $A[i]$ 和 $B[j]$ 结尾的公共子串长度。
• 状态转移：

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } A[i] == B[j] \\ 0 & \text{if } A[i] \neq B[j] \end{cases}$$

------



2. 常用技巧



• 答案位置

最终答案不是 $dp[n][m]$，而是矩阵中的全局最大值 $\max(dp[i][j])$。

• 降维处理

由于只需要 $dp[i-1][j-1]$，可以用一维数组从后往前遍历来优化空间。

• 变体：最大重复子数组

3. 代码模板

// 最长公共子串模板
int maxLen = 0;
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;
            maxLen = max(maxLen, dp[i][j]); // 实时更新全局最大
        } else {
            dp[i][j] = 0; // 核心：断裂归零
        }
    }
}