10 线性动态规划专项（二）

GESP C++ 六级：线性动态规划专项（二）

核心目标：在掌握一维线性 DP 的基础上，深入掌握双调序列（LIS + LDS）、最长公共子序列（LCS） 、划分型 DP三大高频模型，能独立完成状态定义、转移方程推导与代码实现。
双调序列是“先升后降”，用正反两次 LIS 拼出山顶；LCS 是“两个序列配对”，字符相同继承左上角+1，不同取上/左较大值；划分 DP 是“切蛋糕”，枚举最后一刀的起点，把大问题拆成前缀子问题。

一、考纲定位

根据 CCF 官方考纲，六级明确要求掌握“简单动态规划（一维动态规划、简单背包问题） ”。在 GESP 六级真题中，动态规划的考查已经从“单序列一维 DP”扩展到“双序列二维 DP”和“划分型 DP”，核心模型包括：

模型	重要程度	典型真题
双调序列（LIS + LDS）	★★★★★	登山问题、合唱队形
最长公共子序列（LCS）		公共子序列
划分型 DP		划分字符串、学习小组、计算得分
网格路径 DP	★★★★☆	数字三角形、最短路径计数

六级 DP 的命题趋势是“题面千变万化，底层模型不变”。很多同学刷 GESP 六级时会有一种体验：题面千变万化，但最后“都在让你把东西切成一段一段”。掌握这三个核心模型，就能覆盖绝大多数六级 DP 编程题。

二、双调序列（LIS + LDS）

2.1 问题模型

双调序列（也叫“山形序列”“合唱队形”）要求序列先严格递增，后严格递减。经典场景是登山：队员按照顺序浏览景点，一旦开始下山就不再向上走，求最多能浏览多少景点。

核心思路：将问题分解为两个部分——

正向求以每个位置结尾的最长上升子序列（up[i]）
反向求以每个位置开头的最长下降子序列（down[i]）

对于每个位置 i，如果以它作为“山顶”，最大浏览景点数为：

up[i] + down[i] - 1

为什么减 1？因为 i 这个位置在 up 和 down 中被计算了两次。

2.2 代码实现

int n, a[1005];
int up[1005], down[1005];

// 正向 LIS：up[i] 表示以 i 结尾的最长上升子序列长度
for (int i = 0; i < n; i++) {
    up[i] = 1;
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) {
            up[i] = max(up[i], up[j] + 1);
        }
    }
}

// 反向 LDS：down[i] 表示以 i 开头的最长下降子序列长度
for (int i = n - 1; i >= 0; i--) {
    down[i] = 1;
    for (int j = n - 1; j > i; j--) {
        if (a[j] < a[i]) {
            down[i] = max(down[i], down[j] + 1);
        }
    }
}

// 枚举山顶
int ans = 0;
for (int i = 0; i < n; i++) {
    ans = max(ans, up[i] + down[i] - 1);
}
cout << ans << endl;

关键细节：

up 的转移是 a[j] < a[i]（严格上升）。
down 的转移是 a[j] < a[i]（从 i 出发往右看，右边的元素比 i 小，构成下降）。
答案不是 up[n-1] 或 down[0]，而是所有位置作为山顶的最大值。

2.3 真题对接

登山问题（NOI OpenJudge 1996）：题目要求找出一条先上升后下降的路径，且不访问海拔相同的连续景点。这正是双调序列的标准模型。

合唱队形（洛谷 P1091）：要求队列呈现先严格递增、后严格递减的“山峰形”，求最少移走多少人。答案 = n - max(up[i] + down[i] - 1)。

三、最长公共子序列（LCS）

3.1 问题模型

给定两个序列（字符串），求它们最长的公共子序列。子序列不要求连续，但顺序不能改变。例如 abcfbc 和 abfcab 的最长公共子序列是 abcb，长度为 4。

3.2 二维 DP 分析

状态：dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度
转移：
- 如果 s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
- 如果 s1[i-1] != s2[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界：dp[0][j] = 0，dp[i][0] = 0
答案：dp[n][m]

为什么字符不同时要取 max(dp[i-1][j], dp[i][j-1]) ？因为当前两个字符不相同，它们不可能同时贡献到公共子序列中，所以要么放弃 s1 的最后一个字符，要么放弃 s2 的最后一个字符，取两种情况中更优的。

3.3 代码实现

int dp[1005][1005];

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

3.4 LCS 与 LIS 的区别

对比项	LIS	LCS
输入	一个序列	两个序列
状态维度	一维	二维
核心操作	找比自己小的前驱	比较两个字符是否相同
时间复杂度	O(n²)	O(n×m)
典型应用	最长上升子序列	DNA 序列比对、文章查重

LCS 是很多经典问题的原型，例如 DNA 序列比对、比较基因相似度、文章查重、聊天记录分析等。

四、划分型 DP

4.1 核心模型

划分型 DP 的典型场景是：给定一个线性结构（数组或字符串），把它切成若干个连续段，每段产生一个贡献或代价，要求最大化或最小化目标。

划分 DP 的核心永远是两件事：状态怎么定义（用什么维度描述“做到哪了”） ，以及最后一刀在哪里切（枚举分割点） 。

4.2 两种常见套路

套路一：段数固定的划分（二维 DP）

状态：dp[i][j] 表示“前 i 个元素，划分成 j 段时的最优值”。

转移：dp[i][j] = opt_{k < i} { dp[k][j-1] + cost(k+1, i) }

记忆口诀：“二维划分 = 前 i 个 + 切 j 段 + 枚举最后一段从哪来”。

套路二：段数不固定的划分（一维 DP）

状态：dp[i] 表示“前 i 个元素切成若干段的最优值”。

转移：dp[i] = opt_{k < i} { dp[k] + cost(k+1, i) }，并且必须满足最后一段合法。

记忆口诀：“一维划分 = 只管前 i 最优，最后一段从 k+1 到 i”。

4.3 真题：划分字符串

题目描述：将字符串划分为若干子串，使得子串中每个字母至多出现一次，并最大化子串价值之和。

DP 分析：

状态：dp[i] 表示前 i 个字符划分后的最大价值之和
转移：dp[i] = max(dp[i], dp[j-1] + a[i-j+1])，其中 j 是最后一个子串的起点，i-j+1 是最后一个子串的长度
约束：从 j 到 i 的子串不能有重复字母

代码核心：

dp[0] = 0;
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i-1] + a[1];          // 初始：单独成段
    for (int j = 0; j < 26; j++) vis[j] = 0;
    vis[s[i-1] - 'a'] = 1;
    int cnt = 1;
    for (int j = i - 1; j >= 1; j--) {
        if (vis[s[j-1] - 'a'] == 1) break;   // 重复字母，停止
        vis[s[j-1] - 'a'] = 1;
        cnt++;
        dp[i] = max(dp[i], dp[j-1] + a[cnt]);
    }
}
cout << dp[n];

关键细节：枚举最后一段起点时，一旦遇到重复字母就 break，因为再往前扩展一定也不合法。

4.4 真题：计算得分

题目描述：给定字符串，其中包含若干 abc 子串，每个 abc 子串有对应的得分，求最大总得分。

DP 分析：预处理出含有 k 个 abc 的字符串的最大得分：P[k] = max_{i=0}^{i<=k} (P[k-i] + P[i])。

这本质上是一个划分型 DP：把 k 个 abc 分成两部分，分别求最优后合并。

4.5 真题：学习小组（2025年6月）

题目描述：将 n 名学生分成若干个连续编号的小组，每个小组人数不能超过 m，每个小组有对应的奖励值，求分组后奖励值之和的最大值。

DP 分析：

状态：dp[i] 表示前 i 名学生分组后的最大奖励
转移：dp[i] = max(dp[i], dp[j-1] + a[i-j+1])，其中 i-j+1 ≤ m

五、易错点汇总

双调序列的 up 和 down 方向搞反：up[i] 是“以 i 结尾”的 LIS，down[i] 是“以 i 开头”的 LDS。down 需要反向遍历。
忘记减 1：up[i] + down[i] - 1，山顶被算了两次。
LCS 的边界遗漏：dp[0][j] 和 dp[i][0] 必须初始化为 0。
LCS 中字符下标混淆：dp[i][j] 对应 s1[i-1] 和 s2[j-1]，不是 s1[i] 和 s2[j]。
划分 DP 的段数固定与不固定混淆：段数固定用二维 dp[i][j]，段数不固定用一维 dp[i]。
划分 DP 中 cost 函数计算错误：cost(k+1, i) 表示最后一段从 k+1 到 i，注意下标边界。
划分 DP 的枚举方向：枚举最后一段起点时，有些问题需要从后往前枚举（如划分字符串中检查重复字母），有些需要从前往后（如学习小组中检查人数上限）。
整数溢出：涉及累加或乘积的 DP，用 long long。
双调序列要求“严格”：a[j] < a[i] 是严格小于，不能写成 <=。
划分 DP 的初始化：最大化问题 dp[0] = 0，其余初始化为 -INF；最小化问题初始化为 +INF。

六、速查表

模型	状态定义	转移方程	答案位置
双调序列	`up[i]` 以 i 结尾 LIS，`down[i]` 以 i 开头 LDS	`up[i]=max(up[j])+1`（j<i, a[j]<a[i]）	`max(up[i]+down[i]-1)`
LCS	`dp[i][j]` 前 i 和前 j 的 LCS 长度	相同：`dp[i-1][j-1]+1`；不同：`max(dp[i-1][j], dp[i][j-1])`	`dp[n][m]`
划分 DP（段数不固定）	`dp[i]` 前 i 个元素的最优值	`dp[i]=opt(dp[k]+cost(k+1,i))`	`dp[n]`
划分 DP（段数固定）	`dp[i][j]` 前 i 个分 j 段	`dp[i][j]=opt(dp[k][j-1]+cost(k+1,i))`	`dp[n][K]`

七、总结

线性动态规划专项（二）的三个核心模型，覆盖了 GESP 六级 DP 编程题的绝大多数场景。

双调序列 = 正向 LIS + 反向 LDS，山顶公式 up[i]+down[i]-1。
LCS 是二维 DP，字符相同继承左上角加 1，不同取上/左最大值。
划分 DP 的核心是“枚举最后一刀”，把大问题拆成前缀子问题。
段数不固定用一维 dp[i]，段数固定用二维 dp[i][j]。
双调序列中 down 数组需要反向遍历。
LCS 的字符下标是 i-1 和 j-1，不是 i 和 j。
划分 DP 的 cost(k+1, i) 表示最后一段，注意下标边界。
双调序列要求严格上升/下降，用 < 不用 <=。
划分 DP 的初始化：最大化 dp[0]=0，其余 -INF。
多练“登山问题”“公共子序列”“划分字符串”“计算得分”四类题。

复习建议：先把双调序列的“正反两次 LIS”和 LCS 的二维转移写熟；再重点攻克划分 DP，理解“枚举最后一刀”的核心思想；然后对照“划分字符串”和“计算得分”两道真题，体会 cost 函数的设计方式。考试中先判断题目属于哪个模型，再套用对应的状态定义和转移方程，最后检查边界和初始化。