(2) 复杂动态规划

GESP C++七级考试大纲的第2条考点是整个七级的“重头戏”——复杂动态规划。相比于低级别的线性DP，七级要求掌握更复杂的模型（如区间DP）以及处理两个序列的问题（LCS），同时对空间复杂度优化提出了明确要求。

Important

（2）掌握复杂动态规划（二维动态规划、动态规划最值优化）。包括区间动态规划、最长上升子序列（LIS）、最长公共子序列（LCS）等内容，理解基于滚动数组等降低动态规划空间复杂度的方法。

Warning

动态规划（DP）的核心在于状态定义和状态转移方程。七级考试中，题目往往不会直接告诉你“我是DP题”，需要你通过观察“最优子结构”和“重叠子问题”来发现。

Warning

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

一、最长上升子序列 (LIS)

LIS (Longest Increasing Subsequence) 是线性DP的经典问题。虽然存在 $O(n \log n)$ 的贪心+二分这种更优解法，但在七级考纲的DP语境下，首先要掌握的是 $O(n^2)$ 的朴素DP解法。

1.1 问题定义与示例

子序列 (Subsequence)：从原序列中删去若干元素（也可以不删），剩下的元素按原顺序排列而成的序列。注意不要求连续。
上升 (Increasing)：子序列中的元素严格单调递增（即 $a_1 < a_2 < \dots < a_k$ ）。
示例：序列 $A = [10, 9, 2, 5, 3, 7, 101, 18]$ $A = [10, 9, 2, 5, 3, 7, 101, 18]$
- [10, 2, 3] 是子序列，但不是上升的。
- [2, 5, 7, 101] 是一个上升子序列，长度为 4。
- [2, 3, 7, 18] 也是一个上升子序列，长度为 4。
- 最长上升子序列的长度 (LIS) 就是 4。

1.2 状态与转移逻辑详解

通俗来理解，LIS 就像是“接龙游戏”：我们希望把当前的数字拼在前面某个比它小的数字后面，从而让队伍变得越长越好。

状态定义： $dp[i]$ 表示必须以第 $i$ 个元素 a[i] 结尾的最长上升子序列的长度。
- 关键点：为什么状态必须包含“以 a[i] 结尾”？因为只有确定了最后一个数字是谁，我们才能判断下一个数字能不能接在它后面（必须比它大才能接）。
状态转移（怎么算）：想要计算 $dp[i]$ （即以 a[i] 结尾的最长长度），我们需要回头看它前面的所有元素 a[j] (其中 $j < i$ )：
1. 筛选 (Check)：首先，只有当前面的数 a[j] 比当前的 a[i] 小 ( $a[j] < a[i]$ ) 时，a[i] 才能接在 a[j] 后面形成上升序列。
2. 接龙 (Extend)：如果能接上，那么以 a[i] 结尾的新长度就是 dp[j] + 1。（这里 dp[j] 是本来以 a[j] 结尾的长度，+1 是加上 a[i] 自己）。
3. 选最优 (Maximize)：前面的 j 可能有很多个满足条件的，我们要从这些能接的队伍里，挑一个本来就最长的，即取 $\max(dp[j])$ 。
4. 保底 (Base Case)：如果前面找不到任何比 a[i] 小的数，说明 a[i] 没法接在任何人后面，那它自己只能自立门户，长度为 1。
公式表达：对于每个 $i$ ，遍历所有 $j < i$ ：
$dp[i] = \max(\{dp[j] \mid a[j] < a[i]\}) + 1$
（如果找不到这样的 $j$ ，则 $dp[i] = 1$ ）
最终答案：整个序列的 LIS 不一定以最后一个元素 a[n] 结尾（比如最后一个数可能是最小的）。所以我们要看以任意位置结尾的所有可能情况，取最大值：
$\text{Answer} = \max(dp[1], dp[2], \dots, dp[n])$

1.3 代码模板 ( $O(n^2)$ )

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

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

    // dp[i] 初始化为 1，至少包含自己
    vector<int> dp(n, 1);
    int ans = 1; // 记录全局最大值

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

    cout << ans << endl;
    return 0;
}

二、最长公共子序列 (LCS)

LCS (Longest Common Subsequence) 是处理两个序列相似度的经典问题，属于典型的二维动态规划。

2.1 问题定义与示例

问题描述：给定两个序列 $A$ 和 $B$ ，求它们的一个最长的公共子序列。注意“子序列”不需要连续，只需保持相对顺序。
示例：
- 序列 $A$ : a b c d e
- 序列 $B$ : a c e f
- 它们的公共子序列包括 a, c, ac, ace 等。
- 最长的就是 ace，长度为 3。

2.2 状态与转移逻辑

状态定义： $dp[i][j]$ 表示序列 $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}$
解释：
- 如果当前两个字符相等，则长度加 1（继承之前的 LCS）。
- 如果不等，则 LCS 可能来自“A 减少一个字符”或者“B 减少一个字符”的情况，取最大值。

2.3 代码模板

// 假设 A 和 B 从下标 1 开始存储，长度分别为 n, m
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;
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}
cout << dp[n][m] << endl;

三、区间动态规划

3.1 什么是区间 DP？

区间 DP 是一种“由小到大”合并的动态规划思想。

核心逻辑：它的求解过程不是像线性 DP 那样从第 1 个走到第 $n$ $n$ 个，而是像拼图或滚雪球——
1. 先解决长度为 1 的小区间（比如单个点）。
2. 再解决长度为 2 的区间（相邻两个点合并）。
3. …
4. 最后合并成长度为 $n$ 的大区间（即整个问题的解）。
状态定义：通常定义 $dp[i][j]$ 为区间 $[i, j]$ (下标从 $i$ 到 $j$ ) 的最优解。
转移思路（切蛋糕）：要把一个大区间 $[i, j]$ 算出来，我们可以把它切成两半： $[i, k]$ 和 $[k+1, j]$ 。我们就枚举所有可能的切割点 $k$ ，找到两部分合并代价最小（或收益最大）的那一种切法。

3.2 经典模型：石子合并

题目：一排石子，每次只能合并相邻的两堆，合并的代价是两堆石子数量之和。求将所有石子合并成一堆的最小代价。

状态定义： $dp[i][j]$ 表示将区间 $[i, j]$ 内的石子合并成一堆的最小代价。
状态转移方程： $dp[i][j] = \min_{k=i}^{j-1} (dp[i][k] + dp[k+1][j]) + \text{cost}(i, j)$ 其中 $k$ 是分割点，将区间分成 $[i, k]$ 和 $[k+1, j]$ 两部分。 $\text{cost}(i, j)$ 是合并这两部分所需的代价（通常是区间和，可用前缀和优化）。

3.3 遍历顺序

这是区间 DP 的易错点！ 不能简单地从 i=1 到 n，从 j=1 到 n。必须按照区间长度 (len) 从小到大枚举，确保计算大区间时，其内部的小区间已经计算完毕。

// 1. 第一层循环：枚举区间长度 (len)
// 区间 DP 必须先算小区间，再算大区间。
// len 从 2 开始，因为 len=1 时只有一堆石子，不需要合并，代价为 0 (初始化已处理)。
for (int len = 2; len <= n; len++) {

    // 2. 第二层循环：枚举区间起点 (i)
    // 确定了长度 len，再确定起点 i，终点 j 也就确定了：j = i + len - 1。
    // i 的最大值要保证 j 不越界 (j <= n)，所以 i <= n - len + 1。
    for (int i = 1; i <= n - len + 1; i++) {
        
        int j = i + len - 1; // 根据起点 i 和长度 len 算出终点 j
        dp[i][j] = 1e9;      // 初始化为一个极大值，方便后面取 min
        
        // 3. 第三层循环：枚举分割点 (k)
        // 尝试在区间 [i, j] 内的每一个位置切一刀，分成 [i, k] 和 [k+1, j]。
        // k 从 i 开始，一直到 j-1 (保证两部分都不为空)。
        for (int k = i; k < j; k++) {
            
            // 状态转移：当前花费 = 左半部分代价 + 右半部分代价 + 这次合并的代价
            // sum[j] - sum[i-1] 是区间 [i, j] 的石子总重量（前缀和优化）
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + (sum[j] - sum[i-1]));
        }
    }
}

3.4 代码逻辑核心解析

为什么要这样写循环？

先枚举长度 len：这是核心！因为 $dp[i][j]$ 的计算依赖于比它包含元素更少的子区间。比如计算长度 5 的区间，必须先知道长度 1, 2, 3, 4 的子区间最优解。如果我们先枚举行 $i$ 再枚举列 $j$ ，可能会导致计算 $dp[i][j]$ 时，需要的子区间 $dp[i][k]$ 或 $dp[k+1][j]$ 还没算出来（特别是当子区间的行号或列号较大时）。
再枚举起点 i：固定了长度，只要滑动起点，就能遍历该长度下的所有区间。
最后枚举分割点 k：这是决策的过程。对于一个确定的区间 $[i, j]$ ，我们在哪里“切一刀”最好？遍历所有切法取最小值。

四、动态规划空间优化：滚动数组

考纲明确要求理解滚动数组。这是为了解决 DP 空间占用过大的问题（如 $10000 \times 10000$ 的 int 数组会爆内存）。

4.1 核心思想：空间不够，时间换空间

在二维动态规划中，我们经常遇到空间复杂度炸裂的问题。

问题：假设 $N=10000$ ，开一个 int dp[10000][10000] 的数组需要约 400MB 内存，题目通常只给 128MB 或 256MB，直接申请会报 MLE (Memory Limit Exceeded)。
观察：在计算第 $i$ 行状态 ( $dp[i][\dots]$ ) 时，通常只用到第 $i-1$ 行 ( $dp[i-1][\dots]$ ) 的数据。至于第 $i-2$ 行、第 $i-3$ 行……它们已经失去利用价值了。
解决策略（滚动更新）：虽然我们逻辑上需要 $N$ $N$ 行，但物理上我们只需要2行空间：
- 一行存“这一行” (Current) 的数据。
- 一行存“上一行” (Previous) 的数据。
- 算完第 $i$ 行后，它就变成了下一轮的“上一行”，原来的“上一行”就可以扔掉（覆盖）了。

这就好比只有两个脸盆，用来倒水接龙，用完这盆水倒进下一盆，空出来的盆子赶紧去接下一波，周而复始。

4.2 核心技巧：取模运算 (`% 2`)

如何用 2 行数组模拟 $N$ 行？我们利用下标 i 的奇偶性：

当 i 是奇数时，i % 2 = 1，我们用下标 1 的行存数据。
当 i 是偶数时，i % 2 = 0，我们用下标 0 的行存数据。

这样，dp[i] 对应 dp[i % 2]，dp[i-1] 对应 dp[(i-1) % 2]。这两行就会交替使用，永远不会越界。

4.3 示例：LCS 的滚动数组优化

原方程： $dp[i][j]$ 依赖于 $dp[i-1][j-1], dp[i-1][j], dp[i][j-1]$ 。我们可以将第一维从 $N$ 压缩到 2。

int dp[2][10005]; // 第一维度只需要 2

for (int i = 1; i <= n; i++) {
    int cur = i % 2;        // 当前行物理下标 (0 或 1)
    int prev = (i - 1) % 2; // 上一行物理下标 (1 或 0)
    
    for (int j = 1; j <= m; j++) {
        if (A[i] == B[j]) {
            dp[cur][j] = dp[prev][j-1] + 1;
        } else {
            dp[cur][j] = max(dp[prev][j], dp[cur][j-1]);
        }
    }
}
// 最终答案：注意是 dp[n % 2][m]，不是 dp[1][m] 或 dp[0][m]
cout << dp[n % 2][m] << endl;

五、备考总结

模板熟记：LIS, LCS, 0/1背包, 区间DP（石子合并）是必须背下来的模板。
边界条件：注意 DP 数组的初始化（最大值、最小值或 0）以及下标是从 0 开始还是从 1 开始。区间 DP 尤其推荐从 1 开始。
空间计算：考试时要算一下内存。int dp[5000][5000] 大约是 $25000000 \times 4B \approx 100MB$ ，通常接近或超过限制（128MB/256MB）。这时候必须用滚动数组。
调试技巧：DP 不对时，打印出 dp 数组的小规模数据（如 $n=5$ ），手动模拟推导过程，看哪里偏离了预期。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年1月25日

(1) 数学库常用函数 (3) 图论基础与遍历算法