11 字符串动态规划

GESP C++ 六级讲义：字符串动态规划

核心目标：掌握字符串DP的核心模型——划分型DP、最长公共子序列（LCS）、编辑距离、回文分割，能独立完成状态定义、转移方程推导与代码实现，能辨析不同模型的适用场景。
字符串DP的本质是“在字符串上做决策”——划分DP枚举最后一刀，LCS比较两个字符是否相同，编辑距离考虑增删改三种操作，回文分割预处理回文子串后做区间划分；核心都是四步法：定状态、写方程、找边界、定顺序。

一、考纲定位

根据CCF官方考纲，六级明确要求掌握“简单动态规划（一维动态规划、简单背包问题） ”。在GESP六级真题中，字符串DP是编程题的高频考查方向。2025年9月六级的“划分字符串”就是一道典型的字符串DP题。

字符串DP在六级考试中的考查分布：

考点	重要程度	典型考法
划分型DP（字符串切段）	★★★★★	编程题高频
最长公共子序列（LCS）	★★★★★	编程题、选择题
编辑距离	★★★★☆	编程题、选择题
回文子串判断与回文分割	★★★★☆	编程题
字符串DP的状态定义	★★★★★	代码填空

二、核心模型一：划分型DP

2.1 问题模型

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

2025年9月六级真题“划分字符串”就是标准模型：给定字符串 s 和长度价值数组 a，将 s 划分为若干子串，使得子串中每个字母至多出现一次，求最大价值之和。

2.2 DP分析

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

转移方程的含义：枚举最后一段的起点 j，把问题拆成“前 j-1 个字符的最优划分”+“最后一段的贡献”。

2.3 代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[111111], dp[111111];
string s;

signed main() {
    int n;
    cin >> n >> s;
    s = " " + s;                        // 下标从1开始
    for (int i = 1; i <= n; i++) cin >> a[i];

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i-1] + a[1];         // 初始：单独成段
        set<char> st;
        st.insert(s[i]);
        for (int j = i - 1; j >= 1; j--) {
            if (st.count(s[j])) break;   // 重复字母，停止扩展
            st.insert(s[j]);
            dp[i] = max(dp[i], dp[j-1] + a[i - j + 1]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

关键细节：枚举最后一段起点时，一旦遇到重复字母就 break，因为再往前扩展一定也不合法。由于字母只有26个小写字母，内层循环最多遍历27次就必定遇到重复字符，因此总体时间复杂度为 O(26n)，远优于表面上的 O(n²)。

2.4 同类真题：计算得分

预处理含有 k 个 abc 的字符串的最大得分：P[k] = max(P[k-i] + P[i])，其中 i 从 0 到 k。这本质上也是划分型DP——把 k 个 abc 分成两部分，分别求最优后合并。

三、核心模型二：最长公共子序列（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)

四、核心模型三：编辑距离

4.1 问题模型

给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace） 一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

4.2 DP分析

状态：dp[i][j] 表示将 s1 的前 i 个字符转换为 s2 的前 j 个字符所需的最少操作次数
转移：
- 如果 s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1]（无需操作）
- 如果 s1[i-1] != s2[j-1]：
  - 删除：dp[i-1][j] + 1
  - 插入：dp[i][j-1] + 1
  - 替换：dp[i-1][j-1] + 1
  - 取三者最小值
边界：dp[i][0] = i（删除 i 个字符），dp[0][j] = j（插入 j 个字符）
答案：dp[n][m]

4.3 代码实现

int dp[1005][1005];

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 (s1[i-1] == s2[j-1]) {
            dp[i][j] = dp[i-1][j-1];
        } else {
            dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    }
}
cout << dp[n][m] << endl;

三种操作的对应关系：

删除 s1[i]：dp[i-1][j]
插入 s2[j]：dp[i][j-1]
替换 s1[i] 为 s2[j]：dp[i-1][j-1]

五、核心模型四：回文分割与回文子串

5.1 回文子串判断

用 isPal[i][j] 表示子串 s[i..j] 是否为回文。转移：

如果 s[i] == s[j]：isPal[i][j] = isPal[i+1][j-1]（长度 > 2）或 true（长度 ≤ 2）
如果 s[i] != s[j]：false

bool isPal[1005][1005];

for (int i = 0; i < n; i++) isPal[i][i] = true;
for (int i = 0; i < n - 1; i++) isPal[i][i+1] = (s[i] == s[i+1]);

for (int len = 3; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        isPal[i][j] = (s[i] == s[j]) && isPal[i+1][j-1];
    }
}

5.2 回文分割

问题：将字符串分割成若干回文子串，求最少分割次数。

DP分析：

状态：dp[i] 表示前 i 个字符的最小分割次数
转移：dp[i] = min(dp[i], dp[j] + 1)，其中 s[j..i-1] 是回文
边界：dp[0] = 0
答案：dp[n]

int dp[1005];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
    dp[i] = i;   // 最坏情况：每个字符单独成段
    for (int j = 0; j < i; j++) {
        if (isPal[j][i-1]) {
            dp[i] = min(dp[i], dp[j] + 1);
        }
    }
}

5.3 回文拼接

预处理所有可能的子串是否为回文后，枚举所有子串对，利用预处理结果快速判断拼接后的字符串是否为回文。

六、字符串DP的解题框架

6.1 四步法应用

步骤	划分DP	LCS	编辑距离
定状态	`dp[i]` 前 i 个字符	`dp[i][j]` 前 i 和前 j	`dp[i][j]` 前 i 转前 j
写方程	`dp[j-1] + a[i-j+1]`	相同继承，不同取max	相同继承，不同取min
找边界	`dp[0] = 0`	`dp[0][j] = dp[i][0] = 0`	`dp[i][0] = i`
定顺序	i 从小到大	i、j 都从小到大

6.2 状态定义的常见模式

模式	状态定义	典型问题
前缀划分	`dp[i]` 前 i 个字符的最优划分	划分字符串、回文分割
双序列匹配	`dp[i][j]` 两个序列前 i 和前 j	LCS、编辑距离
区间回文	`dp[i][j]` 子串 s[i..j] 的状态	回文子串判断

七、易错点汇总

划分DP的重复字母判断：内层循环遇到重复字母立即 break，因为再往前扩展一定也不合法。
划分DP的边界条件：j == 0 时需要特殊判断，dp[j-1] 会越界。
LCS的边界遗漏：dp[0][j] 和 dp[i][0] 必须初始化为 0。
LCS中字符下标混淆：dp[i][j] 对应 s1[i-1] 和 s2[j-1]，不是 s1[i] 和 s2[j]。
编辑距离的边界：dp[i][0] = i，dp[0][j] = j，不能忘记。
编辑距离的三种操作：删除、插入、替换要分别对应正确的状态转移。
回文子串的长度遍历顺序：必须从长度 1 开始，逐步增大，因为 isPal[i][j] 依赖 isPal[i+1][j-1]。
回文分割的初始值：dp[i] = i 是最坏情况（每个字符单独成段），不能初始化为 0 或 -1。
整数溢出：涉及累加或最小值的DP，用 long long 或 INF。
时间复杂度估算：划分DP表面是 O(n²)，但由于内层会提前 break，实际复杂度远低于 n²。

八、速查表

模型	状态定义	转移方程	答案位置
划分字符串	`dp[i]` 前 i 个字符最大价值	`dp[i] = max(dp[j-1] + a[i-j+1])`	`dp[n]`
计算得分	`P[k]` k 个 abc 最大得分	`P[k] = max(P[k-i] + P[i])`	`P[k]`
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[i][j]` 前 i 转前 j 最少操作	相同：`dp[i-1][j-1]`；不同：`1+min(删,插,替)`	`dp[n][m]`
回文子串	`isPal[i][j]` 子串是否回文	`s[i]==s[j] && isPal[i+1][j-1]`	预处理
回文分割	`dp[i]` 前 i 个字符最少分割	`dp[i] = min(dp[j] + 1)`，`isPal[j][i-1]`	`dp[n]`

九、总结

字符串动态规划是GESP六级DP模块的核心内容。记住十句话：

字符串DP的本质是在字符串上做决策，核心仍是四步法。
划分型DP的关键是“枚举最后一刀”，把大问题拆成前缀子问题。
划分字符串中，内层循环遇到重复字母立即break，实际复杂度远低于O(n²)。
LCS是二维DP，字符相同继承左上角加1，不同取上/左最大值。
编辑距离考虑增、删、改三种操作，取最小值。
回文子串判断用区间DP，从长度1开始逐步扩展。
回文分割先预处理回文子串，再做划分DP。
LCS和编辑距离的边界条件要单独初始化。
划分DP的dp[j-1]在j==0时需要特判。
多练“划分字符串”“计算得分”“LCS”“编辑距离”四类题。

复习建议：先把划分字符串的代码写熟，理解“枚举最后一刀”的核心思想；再掌握LCS和编辑距离的二维DP转移；然后练习回文子串的预处理和回文分割；最后用真题做限时训练。考试中先判断题目属于哪个模型，再套用对应的状态定义和转移方程，最后检查边界和初始化。