20261007 190323 动态规划系统课程2

动态规划系统课程 · 第二讲：线性 DP 与序列 DP ¶

课程定位：中学生信息学竞赛 / C++ 算法训练

上一讲我们学习了动态规划的基本思想，以及线性 DP、网格 DP、背包 DP、区间 DP、树形 DP 等主要类型。

这一讲开始真正进入系统训练阶段。我们不再只是记忆转移方程，而是训练学生从题目描述出发，独立完成状态设计、转移推导、代码实现和复杂度分析。

本讲重点是：

深入掌握线性 DP 的思考方法。
学会解决最长上升子序列问题。
学会解决最长公共子序列问题。
学会用动态规划解决字符串编辑距离问题。
理解朴素 DP 如何优化，以及为什么优化成立。

一、本讲的学习目标 ¶

完成本讲后，学生应当能够：

判断一道序列问题是否适合使用动态规划。
准确解释 dp[i] 和 dp[i][j] 的含义。
从“最后一个元素”或“最后一个字符”推导状态转移。
独立写出三道典型题目的 C++ 完整代码。
分析时间复杂度与空间复杂度。

建议先掌握 C++ 的数组、vector、循环、函数和 max()、min() 等基本知识。

二、先理解线性 DP 的本质 ¶

线性 DP 中，状态通常按照某个线性顺序进行计算，例如：

dp(1),dp(2),…,dp(n)dp(1),dp(2),\ldots,dp(n)dp(1),dp(2),…,dp(n)

但是，线性 DP 并不意味着转移只能来自前一个状态。

例如：

爬楼梯：可能来自前两个状态。
最大子段和：来自前一个状态或重新开始。
最长上升子序列：可能来自前面任意一个满足条件的位置。
字符串匹配：需要同时考虑两个序列的前缀。

因此，真正需要掌握的是：当前状态依赖哪些已经计算过的状态。

1. 以最长上升子序列为例 ¶

给定序列：

a=(3,1,2,5,4)a=(3,1,2,5,4)a=(3,1,2,5,4)

要求找到一个尽可能长的严格上升子序列。

例如：

1,2,51,2,51,2,5

或者：

1,2,41,2,41,2,4

它们的长度都是 3。

注意两个概念：

子数组（子段）：元素必须连续。
子序列：元素不必连续，但相对顺序不能改变。

动态规划首先要把题目中的“最长”转化成一个精确的状态。

定义：

dp(i)=以 ai 结尾的最长上升子序列长度dp(i)=\text{以 }a_i\text{ 结尾的最长上升子序列长度}dp(i)=以 ai 结尾的最长上升子序列长度

这里的“以 aia_iai 结尾”非常关键。

如果只说 dp[i] 是前 i 个元素的最长上升子序列长度，后续的转移就会不同。

2. 如何推导转移？¶

假设当前元素为 aia_iai。

如果前面有一个元素 aja_jaj，满足：

j<i,aj<aij<i,\qquad a_j<a_ij<i,aj<ai

那么，以 aja_jaj 结尾的上升子序列，可以接上 aia_iai。

因此：

dp(i)=max⁡j<i, aj<ai{dp(j)+1}dp(i)=\max_{j<i,\ a_j<a_i}{dp(j)+1}dp(i)=j<i, aj<aimax{dp(j)+1}

如果没有任何符合条件的前驱，aia_iai 自己就构成长度为 1 的子序列。

所以完整的转移是：

dp(i)=max⁡(1,max⁡j<iaj<ai(dp(j)+1))dp(i)=\max\left(1,\max_{\substack{j<i\a_j<a_i}}(dp(j)+1)\right)dp(i)=max1,j<iaj<aimax(dp(j)+1)

这就是从自然语言推导状态转移方程的过程。

三、例题一：最长上升子序列 LIS ¶

入门进阶

时间复杂度 O(n²)

题目描述 ¶

给定长度为 nnn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an，求最长严格上升子序列的长度。

输入示例

6
3 1 2 5 4 7

输出示例

一种最长上升子序列是：

1,2,4,71,2,4,71,2,4,7

长度为 4。

1. 第一步：设计状态 ¶

定义：

dp(i)=以 ai 结尾的最长上升子序列长度dp(i)=\text{以 }a_i\text{ 结尾的最长上升子序列长度}dp(i)=以 ai 结尾的最长上升子序列长度

为什么不直接定义成整个序列的答案？

因为我们希望在计算当前位置时，能够利用前面已经求出的结果。限制“以 aia_iai 结尾”，就明确了哪些前驱状态可以接到当前元素后面。

2. 第二步：初始化 ¶

每个元素至少可以独立组成一个长度为 1 的子序列。

因此：

dp(i)=1dp(i)=1dp(i)=1

注意，这里的初始化不是随意设置的，而是根据状态的具体含义推导出来的。

3. 第三步：推导转移方程 ¶

对每个位置 iii，枚举它前面的所有位置 jjj。

如果：

aj<aia_j<a_iaj<ai

那么可以把 aia_iai 接到以 aja_jaj 结尾的上升子序列后面：

dp(i)=max⁡(dp(i),dp(j)+1)dp(i)=\max(dp(i),dp(j)+1)dp(i)=max(dp(i),dp(j)+1)

最后，答案不是一定等于 dp[n]，因为最长上升子序列不一定以最后一个元素结尾。

正确答案是：

ans=max⁡1≤i≤ndp(i)\text{ans}=\max_{1\le i\le n}dp(i)ans=1≤i≤nmaxdp(i)

iii	aia_iai	dp(i)dp(i)dp(i)	原因
1	3	1	单独选择 3
2	1	1	前面没有更小元素
3	2	2	`1 → 2`
4	5	3	`1 → 2 → 5`
5	4	3	`1 → 2 → 4`
6	7	4	可以接在 5 或 4 后面

5. C++ 完整实现 ¶

C++

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

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

    int n;
    cin >> n;

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

    vector<int> dp(n, 1);
    int ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度：O(n2)O(n^2)O(n2)，因为每个位置都枚举了此前的位置。
空间复杂度：O(n)O(n)O(n)，用于保存序列和 DP 状态。

6. 进阶：如何优化到 O(n log n)？¶

当 nnn 很大时，O(n2)O(n^2)O(n2) 可能无法通过竞赛中的时间限制。

可以维护一个数组 tails：

tails[k] 表示长度为 k+1 的上升子序列中，可能达到的最小结尾值。

遍历每个元素 x：

如果 x 大于 tails 的最后一个元素，就把它追加到末尾。
否则，用 lower_bound 找到第一个大于等于 x 的元素，并替换它。

为什么可以这样做？

对于相同长度的上升子序列，结尾越小，未来越容易接上更大的元素。因此，我们只需维护每种长度对应的最小结尾值。

注意：tails 并不一定就是某个真实子序列；它维护的是各长度的最优结尾。

C++

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

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

    int n;
    cin >> n;

    vector<int> tails;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        auto it = lower_bound(
            tails.begin(), tails.end(), x
        );

        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << tails.size() << '\n';
    return 0;
}

复杂度：

时间：O(nlog⁡n)O(n\log n)O(nlogn)。
空间：O(n)O(n)O(n)。

教学重点：先让学生真正理解 O(n2)O(n^2)O(n2) 的状态转移，再学习优化。否则很容易只会背 lower_bound，却无法解释它为什么正确。

四、例题二：最长公共子序列 LCS ¶

核心考点

二维线性 DP

LIS 只处理一个序列，而 LCS 同时处理两个序列。

1. 状态设计 ¶

定义：

dp(i)(j)dp(i)(j)dp(i)(j)

表示：

字符串 A 的前 i 个字符与字符串 B 的前 j 个字符之间，最长公共子序列的长度。

例如：

dp(3)(4)dp(3)(4)dp(3)(4)

表示 A 的前三个字符和 B 的前四个字符之间的 LCS 长度。

为什么这里需要二维状态？

因为问题同时取决于两个字符串已经处理到哪里。

2. 初始化 ¶

如果任意一个字符串为空，就不存在非空公共子序列：

dp(0)(j)=0dp(0)(j)=0dp(0)(j)=0

dp(i)(0)=0dp(i)(0)=0dp(i)(0)=0

使用 vector 初始化为 0，可以自然完成这个过程。

3. 推导状态转移 ¶

我们比较两个字符串的最后一个字符。

情况二：最后一个字符不同 ¶

如果：

Ai≠BjA_i\ne B_jAi=Bj

那么一个最长公共子序列不可能同时把这两个不同的末尾字符都作为同一个匹配字符。

我们分别考虑：

不使用 A 的最后一个字符。
不使用 B 的最后一个字符。

于是：

dp(i)(j)=max⁡(dp(i−1)(j),dp(i)(j−1))dp(i)(j)=\max(dp(i-1)(j),dp(i)(j-1))dp(i)(j)=max(dp(i−1)(j),dp(i)(j−1))

合并两种情况，得到完整转移：

dp(i)(j)={dp(i−1)(j−1)+1,Ai=Bjmax⁡(dp(i−1)(j),dp(i)(j−1)),Ai≠Bjdp(i)(j)= \begin{cases} dp(i-1)(j-1)+1,& A_i=B_j\ \max(dp(i-1)(j),dp(i)(j-1)),& A_i\ne B_j \end{cases}dp(i)(j)={dp(i−1)(j−1)+1,max(dp(i−1)(j),dp(i)(j−1)),Ai=BjAi=Bj

4. C++ 完整实现 ¶

C++

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

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

    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    vector<vector<int>> dp(
        n + 1, vector<int>(m + 1, 0)
    );

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == 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]
                );
            }
        }
    }

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

注意：C++ 字符串下标从 0 开始，所以第 i 个字符对应 a[i - 1]。

5. 复杂度分析 ¶

设两个字符串长度分别为 nnn 和 mmm。

时间复杂度：O(nm)O(nm)O(nm)。
空间复杂度：O(nm)O(nm)O(nm)。

6. 进阶：如何恢复具体的公共子序列？¶

有时题目不只要求长度，还要求输出一个最长公共子序列。

可以从 dp[n][m] 开始倒推：

如果 a[i-1] == b[j-1]，记录这个字符，然后令 i--, j--。
否则，如果 dp[i-1][j] >= dp[i][j-1]，令 i--。
否则令 j--。
一直倒推到某个下标为 0。

最后将记录的字符逆序输出。

这说明 DP 不仅能计算答案，也能保存足够的信息来还原解。

五、例题三：字符串编辑距离 Edit Distance ¶

综合应用

二维 DP

这道题进一步训练学生：当当前字符不同的时候，不一定只是在两个已有状态中取最大值，也可能需要比较多种操作的代价。

题目描述 ¶

给定两个字符串 A 和 B。

允许进行三种操作：

插入一个字符。
删除一个字符。
将一个字符替换为另一个字符。

每次操作的代价都是 1。

求把 A 变成 B 的最少操作次数。

例如：

A = horse
B = ros

答案是 3。

一种转换方式是：

horse
rorse    替换 h 为 r
rose     删除 r
ros      删除 e

共进行 3 次操作。

1. 状态设计 ¶

定义：

dp(i)(j)dp(i)(j)dp(i)(j)

表示：

将 A 的前 i 个字符转换为 B 的前 j 个字符所需的最少操作次数。

注意，这里求的是最小代价，不是最长长度。

2. 初始化 ¶

如果目标字符串为空：

dp(i)(0)=idp(i)(0)=idp(i)(0)=i

因为必须删除 A 的全部 i 个字符。

如果原字符串为空：

dp(0)(j)=jdp(0)(j)=jdp(0)(j)=j

因为必须插入 B 的全部 j 个字符。

这一步体现了一个原则：

初始化应当直接从状态的实际含义推导，而不是机械套用统一模板。

3. 推导状态转移 ¶

比较 A 的最后一个字符和 B 的最后一个字符。

情况一：两个字符相同 ¶

如果：

Ai=BjA_i=B_jAi=Bj

就不需要对这个字符额外操作：

dp(i)(j)=dp(i−1)(j−1)dp(i)(j)=dp(i-1)(j-1)dp(i)(j)=dp(i−1)(j−1)

情况二：两个字符不同 ¶

我们有三种选择。

替换

将 A 的最后一个字符替换成 B 的最后一个字符。

dp(i−1)(j−1)+1dp(i-1)(j-1)+1dp(i−1)(j−1)+1

删除

删除 A 的最后一个字符。

dp(i−1)(j)+1dp(i-1)(j)+1dp(i−1)(j)+1

插入

在 A 的末尾插入 B 的最后一个字符。

dp(i)(j−1)+1dp(i)(j-1)+1dp(i)(j−1)+1

因此：

dp(i)(j)=1+min⁡{dp(i−1)(j−1)dp(i−1)(j)dp(i)(j−1)dp(i)(j)=1+\min \begin{cases} dp(i-1)(j-1)\ dp(i-1)(j)\ dp(i)(j-1) \end{cases}dp(i)(j)=1+min⎩⎨⎧dp(i−1)(j−1)dp(i−1)(j)dp(i)(j−1)

这里的三个候选状态分别对应替换、删除和插入，不能遗漏其中任何一种。

4. C++ 完整实现 ¶

C++

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

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

    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    vector<vector<int>> dp(
        n + 1, vector<int>(m + 1, 0)
    );

    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 - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min({
                    dp[i - 1][j - 1],
                    dp[i - 1][j],
                    dp[i][j - 1]
                });
            }
        }
    }

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

5. 复杂度分析 ¶

时间复杂度：O(nm)O(nm)O(nm)。
空间复杂度：O(nm)O(nm)O(nm)。

6. 这道题教会我们什么？¶

LCS 和编辑距离的状态都是：

dp(i)(j)dp(i)(j)dp(i)(j)

但状态含义和转移完全不同。

LCS 求最长长度，因此常使用 max()。
编辑距离求最小操作数，因此常使用 min()。
LCS 在字符相同时增加长度。
编辑距离在字符相同时不增加操作次数。

不能因为两道题都是二维 DP，就直接套用同一套转移方程。

六、三道题的横向比较 ¶

这是本讲最重要的总结之一。

比较内容	LIS	LCS	编辑距离
处理对象	一个序列	两个序列	两个字符串
状态	`dp[i]`	`dp[i][j]`	`dp[i][j]`
状态含义	以 i 结尾的最长上升子序列	两个前缀的最长公共子序列	两个前缀的最小转换代价
主要转移	枚举前驱	比较末尾字符	枚举三种操作
优化目标	最大值	最大值	最小值
朴素时间复杂度	O(n2)O(n^2)O(n2)	O(nm)O(nm)O(nm)	O(nm)O(nm)O(nm)

这三道题分别训练三种思维：

LIS：从前面所有合法状态中寻找最优前驱。
LCS：通过两个序列的末尾关系进行分类讨论。
编辑距离：将当前操作拆成若干种可能，取最优代价。

如果学生能理解这三种思维，后面学习背包 DP、区间 DP 时就会更容易。

七、课后练习：检查是否真正掌握 ¶

建议先独立完成，不要立即查看代码。

练习 1：LIS 的状态转移

序列为 2、5、3、4。按照 O(n²) 的方法，最终的最长上升子序列长度是多少？

练习 2：LCS 的初始化

对于两个字符串的最长公共子序列，dp(i)(0) 应该是多少？

练习 3：编辑距离

把空字符串转换成长度为 4 的字符串，最少需要多少次插入操作？

0 次

3 次

4 次

检查答案

八、下一讲学什么？¶

下一讲建议进入第三讲：背包 DP 系统精讲。

背包 DP 是中学生信息学竞赛最值得投入时间的专题之一，后续将按照以下顺序展开：

从暴力枚举理解 01 背包。
推导二维状态转移，再优化成一维数组。
彻底理解为什么 01 背包必须倒序遍历。
完全背包：为什么循环方向变成正序。
多重背包：二进制拆分优化。
分组背包、二维费用背包与方案计数。
用 C++ 完整实现，并通过手工模拟、边界测试和复杂度分析检验程序。

本讲的核心要求：不要只记住三个题目的代码。请尝试不看答案，独立写出每道题的状态定义、初始化和状态转移方程。能解释“为什么”，才算真正学会动态规划。

20261007 190323 动态规划系统课程2

动态规划系统课程 · 第二讲：线性 DP 与序列 DP ¶

一、本讲的学习目标 ¶

二、先理解线性 DP 的本质 ¶

1. 以最长上升子序列为例 ¶

2. 如何推导转移？¶

三、例题一：最长上升子序列 LIS ¶

题目描述 ¶

1. 第一步：设计状态 ¶

2. 第二步：初始化 ¶

3. 第三步：推导转移方程 ¶

4. 手工模拟 ¶

5. C++ 完整实现 ¶

6. 进阶：如何优化到 O(n log n)？¶

四、例题二：最长公共子序列 LCS ¶

题目描述 ¶

1. 状态设计 ¶

2. 初始化 ¶

3. 推导状态转移 ¶

情况一：最后一个字符相同 ¶

情况二：最后一个字符不同 ¶

4. C++ 完整实现 ¶

5. 复杂度分析 ¶

6. 进阶：如何恢复具体的公共子序列？¶

五、例题三：字符串编辑距离 Edit Distance ¶

题目描述 ¶

1. 状态设计 ¶

2. 初始化 ¶

3. 推导状态转移 ¶

情况一：两个字符相同 ¶

情况二：两个字符不同 ¶

4. C++ 完整实现 ¶

5. 复杂度分析 ¶

6. 这道题教会我们什么？¶

六、三道题的横向比较 ¶

七、课后练习：检查是否真正掌握 ¶

八、下一讲学什么？¶