LIS与LCS专题复习笔记

动态规划经典模型：最长上升子序列(LIS)与最长公共子序列(LCS)

包含13道经典题目，涵盖基础模板到变种应用

---

目录

1. 知识点概览
2. LIS 专题
   • 基础模板：O(n²) 解法
   • 优化模板：O(nlogn) 解法
   • 变种题目分析
3. LCS 专题
   • 基础模板：O(n²) 解法
   • 优化解法：排列的LCS
4. 编辑距离
5. 综合练习

---

一、知识点概览

题目分类

类型	题目编号	核心考点
LIS基础	P2856	模板题，O(n²)
LIS优化	P5366	大数据，O(nlogn)
LIS变种	P5367, P5423, P2838	求和、修改次数、变形
LIS双向	P2858, P2861, P3774	登山、滑翔翼、合唱队形
LIS应用	P2835	拦截导弹（非递增）
LCS基础	P1770	模板题，O(n²)
LCS优化	P1771, P4598	大数据、字符串LCS
编辑距离	P2851	DP变形

---

二、LIS 专题

1. 基础模板：最长上升子序列

题目：P2856 【模板】最长上升子序列

题目简述：给定序列，求最长严格上升子序列长度。n ≤ 1000。

解法一：O(n²) DP

状态定义：

• dp[i] 表示以第 i 个元素结尾的最长上升子序列长度

状态转移：

dp[i] = max(dp[j] + 1)  其中 j < i 且 a[j] < a[i]

关键代码：

int lis = 1;
for (int i = 1; i <= n; i++) {
    dp[i] = 1;  // 初始化：自己就是一个长度为1的子序列
    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {  // 严格上升
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    lis = max(lis, dp[i]);  // 更新全局最大值
}

复杂度：时间 O(n²)，空间 O(n)

---

2. 优化模板：O(nlogn) 解法

题目：P5366 【模板】最长上升子序列2

题目简述：n ≤ 10⁶，必须用 O(nlogn) 解法。

解法：贪心 + 二分

核心思想：

• 维护一个数组 d[]，d[len] 表示长度为 len 的上升子序列的最小末尾元素
• 对于每个元素，用二分找到它能替换的位置

为什么这样是对的？

• 末尾元素越小，后面能接的元素越多
• 我们贪心地让每个长度的末尾尽可能小

关键代码：

int d[MAXN];  // d[i] 表示长度为 i 的上升子序列的最小末尾
int len = 0;  // 当前最长长度

for (int i = 1; i <= n; i++) {
    if (len == 0 || a[i] > d[len]) {
        // 可以接在最后，长度+1
        d[++len] = a[i];
    } else {
        // 二分找到第一个 >= a[i] 的位置，替换它
        int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
    }
}
// 最终 len 就是答案

注意：

• lower_bound 找的是第一个大于等于的位置
• 如果是严格上升，用 lower_bound
• 如果是非严格上升（可以相等），用 upper_bound

复杂度：时间 O(nlogn)，空间 O(n)

---

3. LIS 变种题目

(1) 最大上升子序列和

题目：P5367 最大上升子序列和

题目简述：求上升子序列的最大元素和，而非最大长度。

分析：

• 状态定义改变：dp[i] 表示以 i 结尾的上升子序列的最大和
• 转移方程：dp[i] = max(dp[j] + a[i]) where j < i && a[j] < a[i]

关键代码：

for (int i = 1; i <= n; i++) {
    dp[i] = a[i];  // 初始化：只选自己
    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], dp[j] + a[i]);
        }
    }
    ans = max(ans, dp[i]);
}

注意：最长的不一定和最大！例：[100, 1, 2, 3]，最长是 [1,2,3]，但最大和是 100。

---

(2) 最少修改次数

题目：P5423 最少修改次数

题目简述：修改最少的数字，使数列严格递增。

分析：

• 保留尽量多的元素不动 = 找最长上升子序列
• 答案 = n - LIS长度

考虑序列 [1, 2, 2]，LIS长度是 2，但无法通过修改一个数使其严格递增。

正确做法：

• 需要满足 a[i] - i 严格递增（或非严格）
• 转化为：求 a[i] - i 的最长非递减子序列

---

(3) 友好城市

题目：P2838 友好城市

题目简述：南北两岸各 N 个城市，有 N 对友好关系。要在河上建航道，航道不能交叉，最多建多少条？

分析：

• 航道不交叉 = 选择的城市对在南岸和北岸的顺序一致
• 固定一岸的顺序（如按南岸坐标排序），另一岸的坐标必须上升
• 问题转化为：北岸坐标的最长上升子序列

关键代码：

// 按南岸坐标排序
sort(p + 1, p + n + 1, [](const Pair& a, const Pair& b) {
    return a.south < b.south;
});

// 对北岸坐标求LIS
for (int i = 1; i <= n; i++) {
    b[i] = p[i].north;
}
// 然后对 b[] 求LIS

---

4. 双向 LIS 问题

这类问题的特点：先上升后下降（或反过来）。

(1) 登山问题

题目：P2858 登山

题目简述：按照编号顺序浏览景点，海拔先严格上升再严格下降，最多浏览多少个？

分析：

• 找一个"峰点" i
• 左边是到 i 的上升序列，右边是从 i 开始的下降序列
• 分别求从左到右和从右到左的 LIS

关键代码：

// dp1[i]: 从左到右，以 i 结尾的最长上升子序列
for (int i = 1; i <= n; i++) {
    dp1[i] = 1;
    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
    }
}

// dp2[i]: 从右到左，以 i 开头的最长下降子序列
for (int i = n; i >= 1; i--) {
    dp2[i] = 1;
    for (int j = i + 1; j <= n; j++) {
        if (a[j] < a[i]) dp2[i] = max(dp2[i], dp2[j] + 1);
    }
}

// 枚举峰点
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, dp1[i] + dp2[i] - 1);  // i 被算两次，减1
}

---

(2) 怪盗基德的滑翔翼

题目：P2861 怪盗基德的滑翔翼

题目简述：可以从任意建筑出发，选一个方向滑翔（只能往低飞），最多经过多少建筑？

分析：

• 两个方向：向左或向右
• 向右滑 = 从左到右的 LIS（用高度）
• 向左滑 = 从右到左的 LIS
• 答案 = max(正向LIS, 反向LIS)

---

(3) 合唱队形

题目：P3774 合唱队形

题目简述：n 位同学，要让剩下的排成先上升后下降的队形，最少出列几人？

分析：

• 和登山问题一样
• 答案 = n - max(dp1[i] + dp2[i] - 1)

---

5. 拦截导弹

题目：P2835 拦截导弹

题目简述：

1. 一套系统最多拦截多少导弹？
2. 拦截所有导弹最少需要几套系统？

分析：

第一问：非递增子序列的最大长度

• 因为"每一发都不能高于前一发"
• 就是求最长非递增子序列

第二问：Dilworth 定理

• 最少需要的不上升子序列个数 = 最长上升子序列长度
• 贪心模拟：每次尽可能延长当前系统

关键代码：

// 第一问：最长非递增子序列
// 把"上升"改成"下降或相等"
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);
        }
    }
}

// 第二问：贪心
int systems = 0;
int minHeight[1005];  // 每个系统当前能拦截的最高高度

for (int i = 1; i <= n; i++) {
    bool found = false;
    for (int j = 1; j <= systems; j++) {
        if (minHeight[j] >= a[i]) {  // 可以用这个系统
            minHeight[j] = a[i];
            found = true;
            break;
        }
    }
    if (!found) {  // 需要新系统
        systems++;
        minHeight[systems] = a[i];
    }
}

---

三、LCS 专题

1. 基础模板

题目：P1770 【模板】最长公共子序列1

题目简述：求两个排列的最长公共子序列。n ≤ 1000。

解法：O(n²) DP

状态定义：

• dp[i][j] 表示 A 的前 i 个和 B 的前 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])

关键代码：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; 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]);
        }
    }
}
// 答案是 dp[n][n]

复杂度：时间 O(n²)，空间 O(n²)

---

2. 优化：排列的 LCS

题目：P1771 最长公共子序列2

题目简述：n ≤ 100000，排列的 LCS。

分析：

• 排列的特点：元素不重复，都是 1~n
• 可以把问题转化为 LIS！

转化方法：

• 设 A 是 [3, 1, 2]，B 是 [1, 2, 3]
• 记录 A 中每个值的位置：pos[3]=1, pos[1]=2, pos[2]=3
• 把 B 转换成 A 中位置序列：[pos[1], pos[2], pos[3]] = [2, 3, 1]
• 求 [2, 3, 1] 的 LIS = 2

为什么正确？

• LCS 保持相对顺序
• 在 A 中的位置递增 = 在 A 中相对顺序正确
• 在 B 中出现 = 在 B 中相对顺序正确
• 所以位置序列的 LIS = LCS

关键代码：

// 记录 A 中每个元素的位置
int pos[MAXN];
for (int i = 1; i <= n; i++) {
    pos[a[i]] = i;
}

// 把 B 转换成位置序列
for (int i = 1; i <= n; i++) {
    b[i] = pos[b[i]];
}

// 对 b[] 求 LIS（用 O(nlogn) 方法）

---

3. 字符串 LCS

题目：P4598 挑选糖果

题目简述：两个字符串，求最长公共子序列。长度 ≤ 100。

分析：

• 就是标准 LCS 问题
• 但如果是排列（字符各不相同），可以用上面的转化方法

---

四、编辑距离

题目：P2851 编辑距离

题目简述：三种操作（插入、删除、替换），将 A 变成 B 的最少操作次数。

状态定义：

• dp[i][j] 表示 A 的前 i 个字符变成 B 的前 j 个字符的最少操作

状态转移：

如果 A[i] == B[j]:
    dp[i][j] = dp[i-1][j-1]  // 不用操作
否则:
    dp[i][j] = min(
        dp[i-1][j] + 1,      // 删除 A[i]
        dp[i][j-1] + 1,      // 在 A[i] 后插入 B[j]
        dp[i-1][j-1] + 1     // 替换 A[i] 为 B[j]
    )

关键代码：

// 初始化：空串变成长度 i 的串需要 i 次插入
for (int i = 0; i <= n; i++) dp[i][0] = i;  // 删除
for (int j = 0; 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], dp[i][j-1], dp[i-1][j-1]}) + 1;
        }
    }
}

---

五、综合练习

题目总结表

题号	题目名	类型	难度	关键技巧
P2856	LIS模板	LIS基础	⭐	O(n²) DP
P5366	LIS模板2	LIS优化	⭐⭐⭐	贪心+二分
P5367	最大上升子序列和	LIS变种	⭐⭐	求和而非长度
P5423	最少修改次数		⭐⭐⭐	转化为 a[i]-i
P2838	友好城市	LIS变形	⭐⭐	排序+转化
P2835	拦截导弹	LIS应用	⭐⭐⭐	非递增+Dilworth
P2858	登山	双向LIS	⭐⭐	正反两次DP
P2861	滑翔翼			选方向的最大值
P3774	合唱队形			n - max
P1770	LCS模板	LCS基础	⭐	O(n²) DP
P1771	LCS2	LCS优化	⭐⭐⭐	转化为LIS
P4598	挑选糖果	LCS	⭐⭐	标准LCS
P2851	编辑距离	DP		三种操作

---

通用模板

LIS O(n²) 模板

int lis(int a[], int n) {
    int ans = 0;
    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);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

LIS O(nlogn) 模板

int lis(int a[], int n) {
    int d[MAXN], len = 0;
    for (int i = 1; i <= n; i++) {
        if (len == 0 || a[i] > d[len]) {
            d[++len] = a[i];
        } else {
            int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
            d[pos] = a[i];
        }
    }
    return len;
}

LCS O(n²) 模板

int lcs(int a[], int b[], int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; 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]);
            }
        }
    }
    return dp[n][n];
}

---

常见错误

1. LIS的"严格"问题

   • 题目说"严格上升"：用 <，二分用 lower_bound
   • 题目说"非严格上升"：用 <=，二分用 upper_bound

2. 双向LIS的重复计算

   • 峰点 i 在正反两个方向都被算了一次
   • 答案要减 1：dp1[i] + dp2[i] - 1

3. LCS的空间优化

   • 可以用滚动数组优化到 O(n) 空间
   • 注意内层循环要从后往前更新

4. 编辑距离的初始化

   • dp[0][j] = j：空串变成 B 的前 j 个字符，需要 j 次插入
   • dp[i][0] = i：A 的前 i 个字符变成空串，需要 i 次删除

---

思维导图

LIS & LCS 专题
├── LIS (最长上升子序列)
│   ├── O(n²) 解法
│   │   └── dp[i] = 以 i 结尾的最长长度
│   ├── O(nlogn) 解法
│   │   └── 贪心 + 二分，维护每个长度的最小末尾
│   └── 变种
│       ├── 最大和：dp[i] = max(dp[j] + a[i])
│       ├── 最少修改：n - LIS
│       ├── 双向：正反两次 DP，找峰点
│       └── 非递增：改判断条件
├── LCS (最长公共子序列)
│   ├── O(n²) 解法
│   │   └── dp[i][j] = A前i个和B前j个的LCS
│   └── 排列优化 O(nlogn)
│       └── 转化为位置序列的 LIS
└── 编辑距离
    └── dp[i][j] = min(删除, 插入, 替换) + 1