【算法基础篇】（三十）线性动态规划封神之路！经典线性 DP 吃透 LIS 与 LCS

前言

在动态规划的浩瀚星海中，有两颗耀眼的 “明星”—— 最长上升子序列（LIS）和最长公共子序列（LCS）。它们被誉为 “经典线性 DP 双子星”，不仅是算法入门的必学内容，更是竞赛题、面试题中的 “常客”。 无论是字节跳动的面试题 “最长递增子序列的长度”，还是 LeetCode 上的高频题 “最长公共子序列”，亦或是衍生出的 “合唱队形”“编辑距离” 等问题，本质上都离不开 LIS 和 LCS 的核心思想。掌握这两个模型，就相当于掌握了线性 DP 的 “半壁江山”。 但很多同学在学习时会陷入困境：LIS 的 O (n²) 暴力版能懂，但 O (nlogn) 优化版看不懂；LCS 的二维 DP 能写，但空间优化不知道怎么下手；遇到衍生题更是无从谈起。 今天这篇文章，就带大家彻底攻克经典线性 DP—— 从 LIS 和 LCS 的基础模型入手，一步步拆解原理、推导公式、编写代码，再通过 3 道衍生题巩固应用，最后总结通用解题模板和优化技巧。全文 5000 + 字，从入门到精通，让你既能理解 “为什么”，又能学会 “怎么做”！

一、经典线性 DP 核心认知：什么是 “经典”？

在正式讲解之前，我们先明确：为什么 LIS 和 LCS 能被称为 “经典线性 DP”？

1.1 经典线性 DP 的定义

经典线性 DP 是线性 DP 的核心分支，其核心特点是：

• 状态依赖具有 “线性关联性”：LIS 的状态依赖前序元素的最长子序列，LCS 的状态依赖两个字符串的前缀子序列；
• 模型通用性极强：很多看似复杂的问题，都能转化为 LIS 或 LCS 模型（如合唱队形 = 双向 LIS，编辑距离 = LCS 的扩展）；
• 优化空间巨大：从暴力 O (n²) 到高效 O (nlogn)，从二维空间到一维空间，优化思路具有普适性，能迁移到其他 DP 问题中。

1.2 经典线性 DP 的解题逻辑

和所有 DP 问题一样，经典线性 DP 的解题依然遵循 “四步曲”：

1. 状态表示：定义 DP 数组的含义（核心中的核心，直接决定后续推导的难易）；
2. 状态转移方程：推导当前状态如何由前序状态计算得出；
3. 初始化：设置边界条件，避免后续计算出现逻辑错误；
4. 填表顺序：保证计算当前状态时，依赖的前序状态已计算完成。

但经典线性 DP 的特殊之处在于：状态表示更 “抽象”（不直接对应具体位置的数值，而是对应 “子序列” 的属性），状态转移更 “灵活”（需要结合子序列的定义推导）。

接下来，我们就按照这个逻辑，逐一拆解 LIS 和 LCS 模型，再拓展到衍生问题。

二、最长上升子序列（LIS）：从暴力到优化，效率翻倍

2.1 什么是 LIS？

最长上升子序列（Longest Increasing Subsequence，简称 LIS）的定义是：给定一个序列，从中按顺序选出一些元素（不要求连续），使得这些元素严格递增，这样的序列就是上升子序列，其中长度最长的就是 LIS。

例如序列[1,2,4,1,3,4]的 LIS 是[1,2,3,4]，长度为 4。

2.2 基础版 LIS（O (n²)）：暴力拆解

题目来源：洛谷 B3637 最长上升子序列

题目链接：https://www.luogu.com.cn/problem/B3637

题目描述：给定长度为 n 的序列，输出其最长上升子序列的长度（n≤5000）。

思路拆解（四步曲）

1. 状态表示

定义dp[i]表示：以第 i 个元素为结尾的所有上升子序列中，最长的长度。

为什么要这样定义？因为上升子序列的 “递增” 特性是通过 “最后一个元素” 体现的 —— 要判断一个元素能否加入子序列，只需对比它与前一个元素的大小。以 i 为结尾的定义，能让状态转移更自然。

2. 状态转移方程

对于dp[i]，我们需要遍历所有 i 之前的元素 j（1≤j<i）：

• 如果a[j] < a[i]：说明 a [i] 可以跟在 a [j] 后面，形成一个更长的上升子序列，此时dp[i] = max(dp[i], dp[j] + 1)；
• 如果a[j] ≥ a[i]：说明 a [i] 不能跟在 a [j] 后面，跳过。

此外，每个元素本身可以作为一个长度为 1 的子序列，因此dp[i]的初始值为 1。

综上，状态转移方程为：dp[i] = max(dp[j] + 1, dp[i])（其中 1≤j<i 且 a [j]<a [i]）

3. 初始化

所有dp[i] = 1（每个元素单独构成一个长度为 1 的子序列）。

4. 填表顺序

从左到右依次计算dp[1]到dp[n]，因为dp[i]依赖前序元素的dp[j]。

最终答案是dp数组中的最大值（因为 LIS 可能以任意元素为结尾）。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5010; // n≤5000，开5010足够
int n;
int a[N]; // 存储原始序列
int dp[N]; // dp[i]：以a[i]为结尾的最长上升子序列长度

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int max_len = 0; // 记录LIS的长度
    for (int i = 1; i <= n; i++) {
        dp[i] = 1; // 初始化：每个元素单独成序列
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]); // 更新最大值
    }

    cout << max_len << endl;
    return 0;
}

代码验证

以示例输入6 1 2 4 1 3 4为例：

• dp[1] = 1（序列 [1]）；
• dp[2] = max(1, dp[1]+1) = 2（序列 [1,2]）；
• dp[3] = max(1, dp[1]+1, dp[2]+1) = 3（序列 [1,2,4]）；
• dp[4] = 1（序列 [1]，前面的元素都比它大或相等）；
• dp[5] = max(1, dp[1]+1, dp[4]+1) = 3（序列 [1,1,3] 或 [1,3]）；
• dp[6] = max(1, dp[1]+1, dp[2]+1, dp[4]+1, dp[5]+1) = 4（序列 [1,2,3,4]）；
• 最终 max_len=4，与示例输出一致。

2.3 优化版 LIS（O (nlogn)）：贪心 + 二分

题目链接：https://ac.nowcoder.com/acm/problem/226831

当 n 增大到 1e5 时，O (n²) 的暴力版会超时（1e10 次运算），此时需要 O (nlogn) 的优化版。

核心思路：贪心 + 二分查找

优化的关键在于：我们不需要知道 LIS 的具体元素，只需要知道 “长度为 x 的上升子序列，最后一个元素的最小值是多少”。

为什么要记录 “最小值”？因为最后一个元素越小，后续元素就越容易加入子序列，从而形成更长的 LIS。

例如，长度为 3 的上升子序列有[1,2,4]和[1,3,4]，前者的最后一个元素是 4，后者是 4，而如果有[1,2,3]，最后一个元素是 3，后续遇到 4 就能形成更长的序列。

因此，我们维护一个数组f，其中f[x]表示：长度为 x 的上升子序列的最后一个元素的最小值。

算法步骤

1. 初始化f数组为空，len=0（当前 LIS 的长度）；
2. 遍历序列中的每个元素a[i]：
   • 如果a[i] > f[len]：说明a[i]可以直接加入最长子序列的末尾，len++，f[len] = a[i]；
   • 否则：在f数组中找到第一个大于等于a[i]的元素，用a[i]替换它（这样能让长度为 x 的子序列的最后一个元素更小，为后续元素留更多空间）；
3. 最终len就是 LIS 的长度。

为什么能用二分查找？

因为f数组是严格递增的！证明如下：

• 假设f[x] ≥ f[x+1]，那么长度为 x+1 的子序列的前 x 个元素构成的子序列，其最后一个元素是f'[x] ≤ f[x+1] ≤ f[x]，这与f[x]是长度为 x 的子序列的最后一个元素的最小值矛盾；
• 因此f数组严格递增，可以用二分查找快速找到目标位置。

代码实现（O (nlogn)）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10; // n≤1e5，开1e5+10足够
int n;
int a[N];
int f[N], len = 0; // f[x]：长度为x的LIS的最后一个元素的最小值

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        if (len == 0 || a[i] > f[len]) {
            // 可以直接加入最长子序列末尾
            f[++len] = a[i];
        } else {
            // 二分查找第一个≥a[i]的元素位置
            int l = 1, r = len;
            while (l < r) {
                int mid = (l + r) / 2;
                if (f[mid] >= a[i]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            // 替换该位置的元素
            f[l] = a[i];
        }
    }

    cout << len << endl;
    return 0;
}

代码验证

以示例输入5 1 2 2 2 3为例：

• 遍历 1：f 为空，f [1]=1，len=1；
• 遍历 2：2>f [1]，f [2]=2，len=2；
• 遍历 2：2≤f [2]，二分找到 f [2]=2，替换为 2，f=[1,2]，len=2；
• 遍历 2：同上，替换 f [2]=2，len=2；
• 遍历 3：3>f [2]，f [3]=3，len=3；
• 最终输出 3，与示例一致。

优化版的优势

• 时间复杂度从 O (n²) 降至 O (nlogn)，能处理 n=1e5 的大数据；
• 空间复杂度仍为 O (n)，但实际使用中f数组的长度为 LIS 的长度，通常远小于 n。

2.4 LIS 衍生题：合唱队形（洛谷 P1091）

题目链接：https://www.luogu.com.cn/problem/P1091

题目描述：n 位同学站成一排，需要选出 k 位同学排成合唱队形（先上升后下降，中间有一个最高点），求最少需要出列的同学数（n≤100）。

思路拆解

合唱队形的本质是：找到一个最高点 i，使得左边是严格上升子序列，右边是严格下降子序列（或严格上升子序列的逆序）。

因此，解题步骤为：

1. 计算f[i]：以 i 为结尾的最长上升子序列长度（从左往右）；
2. 计算g[i]：以 i 为结尾的最长上升子序列长度（从右往左，即原序列的最长下降子序列）；
3. 对于每个 i，合唱队形的最大长度为f[i] + g[i] - 1（i 被计算了两次，需减 1）；
4. 最少出列人数 = n - 最大合唱队形长度。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110; // n≤100，开110足够
int n;
int a[N];
int f[N], g[N]; // f：左到右LIS，g：右到左LIS

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 计算左到右的LIS：f[i]
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }

    // 计算右到左的LIS：g[i]（相当于原序列的最长下降子序列）
    for (int i = n; i >= 1; i--) {
        g[i] = 1;
        for (int j = n; j > i; j--) {
            if (a[j] < a[i]) {
                g[i] = max(g[i], g[j] + 1);
            }
        }
    }

    // 找最大合唱队形长度
    int max_team = 0;
    for (int i = 1; i <= n; i++) {
        max_team = max(max_team, f[i] + g[i] - 1);
    }

    // 最少出列人数 = 总人数 - 最大队形长度
    cout << n - max_team << endl;
    return 0;
}

代码验证

以示例输入8 186 186 150 200 160 130 197 220为例：

• 左到右 LIS：f [4]=3（150,200），f [7]=4（150,160,197），f [8]=5（150,160,197,220）；
• 右到左 LIS：g [4]=3（200,160,130），g [7]=2（197,130），g [8]=1；
• 最大合唱队形长度为 f [4]+g [4]-1=3+3-1=5（150,200,160,130）或 f [7]+g [7]-1=4+2-1=5；
• 最少出列人数 = 8-5=4，与示例输出一致。

三、最长公共子序列（LCS）：双串匹配的核心模型

3.1 什么是 LCS？

最长公共子序列（Longest Common Subsequence，简称 LCS）的定义是：给定两个字符串（或序列），从中按顺序选出一些元素（不要求连续），这些元素在两个字符串中都出现，且顺序一致，这样的序列就是公共子序列，其中长度最长的就是 LCS。

例如字符串s=abccde和t=bcee的 LCS 是bce，长度为 3。

3.2 基础版 LCS（O (nm)）：二维 DP

题目链接：https://ac.nowcoder.com/acm/problem/235624

题目来源：牛客网 牛可乐和最长公共子序列

题目描述：给定两个字符串 s 和 t，输出它们的最长公共子序列长度（单个字符串长度≤5000）。

思路拆解（四步曲）

1. 状态表示

定义dp[i][j]表示：字符串 s 的前 i 个字符（s [1..i]）和字符串 t 的前 j 个字符（t [1..j]）的最长公共子序列长度。

这样定义的原因是：LCS 是基于两个字符串的前缀推导的，前 i 个字符和前 j 个字符的 LCS，能通过更小的前缀子序列推导得出。

2. 状态转移方程

根据 s [i] 和 t [j] 是否相等，分两种情况讨论：

• 如果s[i] == t[j]：说明这个字符是公共子序列的一部分，因此dp[i][j] = dp[i-1][j-1] + 1（前 i-1 和 j-1 的 LCS 长度加 1）；
• 如果s[i] != t[j]：说明这个字符不能同时加入公共子序列，因此dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取 “s 前 i-1 和 t 前 j” 或 “s 前 i 和 t 前 j-1” 的 LCS 最大值）。

这里需要注意：dp[i-1][j-1]已经包含在dp[i-1][j]和dp[i][j-1]中，因此不需要单独考虑。

3. 初始化

• dp[0][j] = 0（s 的前 0 个字符和 t 的前 j 个字符，没有公共子序列）；
• dp[i][0] = 0（t 的前 0 个字符和 s 的前 i 个字符，没有公共子序列）。

4. 填表顺序

从上往下、从左往右依次计算dp[i][j]，因为dp[i][j]依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]，这些状态都在dp[i][j]的上方、左侧和左上方，已提前计算。

代码实现（二维 DP）

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 5010; // 单个字符串长度≤5000，开5010足够
string s, t;
int dp[N][N]; // dp[i][j]：s[1..i]和t[1..j]的LCS长度

int main() {
    while (cin >> s >> t) { // 多组输入，读至文件末尾
        int n = s.size(), m = t.size();
        // 为了方便，将字符串下标从1开始
        s = " " + s;
        t = " " + t;

        // 初始化：dp[0][j]和dp[i][0]均为0，无需额外处理

        // 填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i] == t[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] << endl;
    }
    return 0;
}

代码验证

以示例输入abccde bcee为例：

• s = " abccde"，t = " bcee"；
• dp[2][2] = 1（s[2]='b'，t[2]='b'）；
• dp[4][3] = 2（s[4]='c'，t[3]='c'）；
• dp[6][4] = 3（s[6]='e'，t[4]='e'）；
• 最终输出 3，与示例一致。

3.3 优化版 LCS（O (nm) 时间，O (min (n,m)) 空间）

当 n 和 m 都为 5000 时，二维 DP 数组的空间复杂度为 O (nm) = 2500 万，虽然可以接受，但可以进一步优化到 O (min (n,m))。

优化思路：滚动数组

观察状态转移方程：dp[i][j]只依赖dp[i-1][j]（上一行）、dp[i][j-1]（当前行左侧）、dp[i-1][j-1]（上一行左侧）。因此，我们可以用一维数组dp[j]存储当前行的状态，通过 “从右往左” 填表，避免覆盖dp[j-1]（上一行的值）。

具体步骤

1. 初始化一维数组dp[j] = 0（对应二维 DP 的第一行dp[0][j]）；
2. 遍历 s 的每个字符s[i]：
   • 用变量prev存储dp[j-1]的上一行值（即dp[i-1][j-1]）；
   • 从右往左遍历 t 的每个字符t[j]：
     • 保存当前dp[j]的值到temp（后续作为下一个prev）；
     • 如果s[i] == t[j]：dp[j] = prev + 1；
     • 否则：dp[j] = max(dp[j], dp[j-1])；
     • 更新prev = temp。

代码实现（一维滚动数组）

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 5010;
string s, t;
int dp[N]; // 一维数组，存储当前行的LCS长度

int main() {
    while (cin >> s >> t) {
        int n = s.size(), m = t.size();
        // 确保t是较短的字符串，优化空间（可选）
        if (n < m) swap(s, t);
        n = s.size(), m = t.size();
        s = " " + s;
        t = " " + t;

        // 初始化一维数组
        fill(dp, dp + m + 1, 0);

        for (int i = 1; i <= n; i++) {
            int prev = 0; // 存储dp[i-1][j-1]
            for (int j = 1; j <= m; j++) {
                int temp = dp[j]; // 保存当前dp[j]（即dp[i-1][j]）
                if (s[i] == t[j]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = max(dp[j], dp[j-1]);
                }
                prev = temp; // 更新prev为下一个j的dp[i-1][j-1]
            }
        }

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

优化解析

• 空间复杂度从 O (nm) 降至 O (min (n,m))，当其中一个字符串较短时，优化效果显著；
• 时间复杂度仍为 O (nm)，没有变化；
• 从右往左填表的原因：如果从左往右，dp[j-1]会被当前行的值覆盖，导致dp[j]计算错误；从右往左则不会覆盖上一行的dp[j-1]。

3.4 LCS 衍生题：编辑距离（洛谷 P2758）

题目链接：https://www.luogu.com.cn/problem/P2758

题目描述：给定两个字符串 A 和 B，通过删除、插入、替换三种操作，将 A 转换为 B，求最少操作次数（字符串长度≤2000）。

思路拆解

编辑距离是 LCS 的经典衍生题，其核心思想是：LCS 的长度越长，需要的编辑操作越少。

状态表示

定义dp[i][j]表示：将 A 的前 i 个字符（A [1..i]）转换为 B 的前 j 个字符（B [1..j]）的最少操作次数。

状态转移方程

根据 A [i] 和 B [j] 是否相等，分两种情况讨论：

• 如果A[i] == B[j]：不需要任何操作，dp[i][j] = dp[i-1][j-1]；
• 如果A[i] != B[j]：需要进行以下三种操作之一，取最小值：
  1. 删除 A [i]：dp[i-1][j] + 1（将 A 的前 i-1 个转换为 B 的前 j 个，再删除 A [i]）；
  2. 插入 B [j]：dp[i][j-1] + 1（将 A 的前 i 个转换为 B 的前 j-1 个，再插入 B [j]）；
  3. 替换 A [i] 为 B [j]：dp[i-1][j-1] + 1（将 A 的前 i-1 个转换为 B 的前 j-1 个，再替换 A [i]）。

初始化

• dp[i][0] = i（将 A 的前 i 个字符删除，需要 i 次操作）；
• dp[0][j] = j（将 B 的前 j 个字符插入到 A 中，需要 j 次操作）。

代码实现

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 2010; // 字符串长度≤2000，开2010足够
string a, b;
int dp[N][N]; // dp[i][j]：A[1..i]转换为B[1..j]的最少操作次数

int main() {
    cin >> a >> b;
    int n = a.size(), m = b.size();
    a = " " + a;
    b = " " + b;

    // 初始化
    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(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
            }
        }
    }

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

代码验证

以示例输入 sfdqxbw gfdgw为例：

• a = " sfdqxbw"，b = " gfdgw"；
• dp [7][5] = 4（具体推导略），与示例输出一致。

四、经典线性 DP 通用解题模板

通过 LIS 和 LCS 及其衍生题的学习，我们可以总结出经典线性 DP 的通用解题模板，以后遇到类似问题，直接套用即可：

1. 问题分析

• 判断问题类型：是子序列问题（LIS 类），还是双串匹配问题（LCS 类）；
• 明确目标：求最长长度、最少操作次数，还是其他衍生目标；
• 确定限制条件：是否严格递增 / 递减，是否允许重复元素，是否有操作限制（如编辑距离的三种操作）。

2. 状态表示

• LIS 类（单序列）：dp[i]表示以第 i 个元素为结尾的子序列的属性（长度、最大值等）；
• LCS 类（双序列）：dp[i][j]表示第一个序列前 i 个元素、第二个序列前 j 个元素的子序列的属性。

3. 状态转移方程

• LIS 类：dp[i] = max(dp[j] + 1, dp[i])（j < i 且满足子序列条件）；
• LCS 类：
  • 元素相等：dp[i][j] = dp[i-1][j-1] + 1；
  • 元素不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（或其他操作的最小值）。

4. 初始化

• LIS 类：dp[i] = 1（每个元素单独成序列）；
• LCS 类：dp[i][0] = 0，dp[0][j] = 0（空序列的子序列长度为 0）；
• 衍生题：根据操作定义初始化（如编辑距离的dp[i][0] = i）。

5. 填表顺序

• LIS 类：从左到右；
• LCS 类：从上到下、从左到右；
• 空间优化版：根据状态依赖调整遍历方向（如 LCS 一维版从右往左）。

6. 优化技巧

• 时间优化：LIS 的 O (nlogn) 优化（贪心 + 二分）；
• 空间优化：LCS 的一维滚动数组优化（O (min (n,m)) 空间）；
• 衍生题优化：利用 LIS/LCS 的核心思想，转化问题（如合唱队形 = 双向 LIS）。

总结

经典线性 DP 的难点不在于代码实现，而在于 “状态定义”—— 能否定义出一个合理的 DP 状态，直接决定了后续转移方程的推导难度。 对于 LIS，核心是 “以 i 为结尾” 的状态定义，让子序列的递增特性得以体现；对于 LCS，核心是 “前缀子序列” 的状态定义，让双串的匹配关系得以传递。 而衍生题的关键，则是 “转化思想”—— 将合唱队形转化为双向 LIS，将编辑距离转化为带操作成本的 LCS，将复杂问题拆解为我们熟悉的经典模型。 最后，记住一句话：经典线性 DP 的封神之路，始于 LIS 和 LCS，忠于状态定义，成于优化技巧。多做题、多总结，你也能轻松驾驭这类问题！