Balance 这道字符串平衡计数老题（流传的题号是 17C），我第一次碰到的时候还在用“把字符数量调平”的直觉写贪心，交上去第二行答案错得一塌糊涂。它表面上是道字符串题，骨子里是标准的双目标动态规划：一边求最少的修改次数，一边统计达到这个最少次数的目标串到底有多少个，两个目标必须同时在线维护，不能拆开。字符串长度只有 150，字符集限定在 a、b、c 三个字母，看着规模很小，可一旦把“平衡”这个约束翻译成状态，很多人就会卡在维度设计和方案数去重这两步上。这篇内容面向已经会写基础 DP、但在这类“最优化加计数”题上容易翻车的读者，也适合想把这套模板迁移到其他计数场景的从业者。我会把状态为什么这么设计、代价怎么定义、方案数为什么能直接累加，以及我自己踩过的几个坑都摊开讲清楚。
1. 先把题意嚼碎：两个输出到底在问什么
1.1 一句话还原题意与约束
给定一个只由 a、b、c 组成的字符串 s，长度 n 不超过 150。你可以把任意一个位置上的字符改成 a、b、c 中的另一个字符，每改一个位置算一次操作。要求最终的字符串满足“平衡”：任意两种字符的出现次数之差不超过 1。在满足这个条件的所有字符串里，先找修改次数最少的，输出这个最少次数；再输出能达到这个最少次数的不同目标字符串个数，结果对一个给定的大整数取模。
这里有两个容易读漏的细节。第一，“平衡”约束针对的是整个字符串里三种字符的计数，不是某个子串，也不是相邻字符之间的关系，所以它天然是一个全局计数约束，跟位置顺序无关。第二，输出的是“目标字符串的个数”，不是一个具体的修改方案，也不是修改操作的排列数。理解这两点，后面的状态设计才有落脚点。
把“任意两种字符出现次数之差不超过 1”翻译成数学语言：设最终 a、b、c 的个数分别是 x、y、z，要求 max(x,y,z) - min(x,y,z) ≤ 1，同时 x + y + z = n。这个约束非常强，强到合法的 (x,y,z) 组合只有个位数。以 n = 150 为例，150 = 3 × 50，那么唯一合法的组合就是 (50,50,50)；若 n = 151，合法组合只有 (51,50,50)、(50,51,50)、(50,50,51) 三种。我在草稿纸上算过一遍才意识到：终态的候选集合小得可怜，真正难的不是找终态，而是算清楚从原串走到每个终态要付出多少代价、以及有多少条不同的路径。
1.2 两个目标为什么不能分开算
很多人第一反应是分两步走：先算出最少修改次数，再单独统计方案数。这个思路在本题会直接翻车，原因是最少修改次数本身依赖于“你选择了哪个终态”，而不同终态的最小代价可能相同，也可能不同，你必须把所有终态放在一起比较，才能知道全局最小值是多少。等你知道了最小值，再去统计方案，又得重新跑一遍所有终态，而且统计过程仍然需要知道“走到这个终态的哪些路径代价等于最小值”，这就退化成同一个 DP 做两遍。
更隐蔽的一个坑是把方案数理解成“修改操作的方案数”。举个具体例子：s = “aac”，n = 3，唯一合法终态是 a、b、c 各一个。最少修改次数是 1，因为原串有两个 a、一个 c、零个 b，只需要把一个 a 改成 b。但“改哪个 a”有两个选择：改第一个 a 得到 “bac”，改第二个 a 得到 “abc”，这是两个不同的目标字符串，方案数是 2。如果你按“操作方式”去数，很容易数成 1，或者把两个 a 视为等价而漏算。
再想一层：由于每次操作只影响一个位置，给定原串 s 和给定目标串 t，修改次数就是它们逐位不同的位置数，也就是汉明距离，而且达到这个距离的修改方式唯一——就是把每个不同的位置直接改成目标字符。所以“目标串个数”和“修改方案个数”在本题里其实是同一个数，只要你把目标串数清楚了，操作方案自然就数清楚了。这个等价关系是后面方案数可以直接用路径计数来做的根本原因，值得先在心里钉死。
2. 状态设计：把四维压成三维的关键一步
2.1 最直观的状态长什么样
最朴素的想法是：我从左往右一位一位地决定最终字符串长什么样，同时记录已经用了多少个 a、多少个 b、多少个 c，再记录到目前为止的修改次数。于是状态写成 dp[i][a][b][c]，表示处理完前 i 个位置、最终串里已经放了 a 个 a、b 个 b、c 个 c 时的最小修改次数。转移就是枚举第 i+1 位放什么字符：放 a 就把 a 加一，放 b 就把 b 加一，放 c 就把 c 加一；如果放的字符和原串 s 在这一位上的字符相同，代价加 0，否则加 1。
这个状态是对的，但维度看着吓人：n = 150 时 151⁴ 根本开不下。好在有个显然的恒等式：处理完 i 个位置后，a + b + c 一定等于 i，一个位置只能放一个字符，不可能多放也不可能少放。所以 c 完全由 i 和 a、b 决定，c = i - a - b，第四个维度是冗余的。这一步约简没有任何技巧含量，但它是整道题从“开不下”变成“轻松过”的分水岭。
约简之后状态是 dp[i][a][b]，看起来还是三维，但 i 这一维是“阶段”，可以用滚动数组压掉，实际常驻内存只有两层二维表。更妙的是，i 也可以完全省略：因为 a + b + c = i，只要我知道 a、b、c，就知道当前处理到第几位了。所以最紧凑的写法是 dp[a][b][c]，三维但每一维都限制在 0 到 n，总状态数是 (n+1)³ 级别，n = 150 时大约 344 万个，每个状态存一对（最小代价，方案数），用 32 位整数存，总共约 27 MB。如果内存限制紧，就老老实实滚动 i 这一维，常驻状态数降到两万多个，内存几百 KB，怎么都够。
2.2 维度约简背后的代价核算
我来把数字算细一点，方便你判断到底要不要滚动。按 dp[i][a][b] 的朴素三维写法，i 从 0 到 n，a 从 0 到 i，b 从 0 到 i - a，总状态数是 Σ(i+1)(i+2)/2，i 从 0 到 n-1，这个和约等于 n³/6。n = 150 时是 150³/6 = 562500，乘以每个状态枚举 3 种字符的转移，总转移次数约 168 万次。这个量级对现代机器来说连热身都算不上，哪怕你用 Python 写，只要别写得太离谱，也完全跑得动。
如果按 dp[a][b][c] 的三维写法，状态数是 151³ ≈ 344 万，虽然也开得下，但每次转移都要判断 a+b+c 是否等于当前阶段，逻辑上反而更容易写错。所以我个人的偏好是：主写法用 dp[i][a][b] 加滚动数组，逻辑最贴近“逐位推进”的直觉；如果为了代码短，用 dp[a][b][c] 的记忆化搜索也行，但一定要把“c = i - a - b”这个关系在转移里体现清楚，否则会出现“a+b+c 和 i 对不上”的隐形错误。
这里有个我踩过的坑值得单独说：有人为了省一维，把状态写成 dp[a][b]，然后用一个额外的指针 i 表示当前处理到哪一位，看似省了，其实没省，因为 i 必须跟着转移一起变，本质上还是三维。真正能省掉 i 的前提是“a、b、c 三者之和就等于 i”，也就是说你必须同时知道三个计数，才能反推位置。少一个计数就少一个约束，状态就不完整了。
2.3 代价转移与方案数合并的写法
状态定好之后，转移的核心是一个“双目标合并”操作。对每个状态，我存一对值：cost 表示走到这里的最小修改次数，ways 表示走到这里且修改次数等于 cost 的方案数。当从状态 u 转移到状态 v 时，新代价是 cost(u) + w，其中 w 是这一位放错字符产生的 0 或 1。接下来分三种情况处理：
- 如果新代价小于 v 当前记录的代价，说明找到了一条更优的路径，直接把 v 的代价更新为新代价，方案数更新为 u 的方案数；
- 如果新代价等于 v 当前记录的代价，说明找到了一条同样优的路径，把 u 的方案数累加到 v 的方案数上，注意取模；
- 如果新代价大于 v 当前记录的代价，直接丢弃，这条路径不可能贡献最优解。
这套逻辑和“最短路计数”的写法完全一致，区别只在于边权是 0 或 1，而且图是一个按阶段分层的有向无环图。因为每一层只从上一层转移过来，不存在环，所以不需要任何最短路算法，按阶段递推一遍就完事。
正确性方面有个值得掰开说的点：为什么“路径数”就等于“目标字符串个数”？因为一条路径对应的是“第 1 位放什么、第 2 位放什么……第 n 位放什么”这样一串完整的选择，这串选择唯一确定一个目标字符串；反过来，任何一个目标字符串也唯一对应一条这样的路径。路径的代价恰好是这个目标串与原串的汉明距离。两者是一一对应的双射，所以数路径就是数目标串，不会重复也不会遗漏。这个论证看着简单，但它是整个方案数统计合法性的根基，我在给别人讲这道题时一定要先把这一步讲透，否则后面所有的取模和累加都是空中楼阁。
3. 从零写一版能过的实现
3.1 滚动数组的骨架与清空时机
滚动数组的写法有一个必须遵守的顺序：每一轮开始前，先把“下一层”的表整体重置为“不可达、代价无穷大、方案数为零”，然后再从“当前层”往“下一层”推。如果你图省事只重置了一部分，或者干脆不重置，上一轮残留的状态会污染这一轮，表现出来就是答案偏大或者方案数莫名其妙多出来一堆。
具体到代码，我用 best[2][151][151] 和 ways[2][151][151] 两个数组，第一维是滚动位。初始化时 best 全部置为一个足够大的数（比如 0x3f3f3f3f），ways 全部置 0，然后 best[0][0][0] = 0、ways[0][0][0] = 1，表示“处理了 0 个字符、三种字符都用 0 个、代价为 0”这一种空串方案。这里 ways 的初值必须是 1 而不是 0，原因是“什么都不做”本身就是一种合法方案，如果置 0，后面所有累加都会得到 0，答案永远是 0。这个错误我见过不止一次，而且非常难自查，因为程序不报错、不崩溃，就是答案不对。
还有个小细节：循环里枚举 a 和 b 时，上界不要写成 n，写成当前阶段 i 就够了。写 n 不会错，但会平白多跑很多“a + b > i”的无效状态，虽然这些状态的 best 是无穷大、会被 continue 掉，但白白浪费了判断。规模小的时候无所谓，养成习惯总是好的。
3.2 终态筛选：合法三元组只有个位数
跑完所有位之后，答案不在某一个固定状态里，而是要在一批“合法终态”里挑。所谓合法终态，就是满足 a + b + c = n 且 max - min ≤ 1 的那些 (a,b,c)。前面算过，这样的三元组最多三个。设 q = n / 3，r = n % 3：
- r = 0 时，只有 (q, q, q) 一个；
- r = 1 时，是 (q+1, q, q)、(q, q+1, q)、(q, q, q+1) 三个；
- r = 2 时，是 (q+1, q+1, q)、(q+1, q, q+1)、(q, q+1, q+1) 三个。
代码里我一般不去手写这三种情况，而是直接双重循环枚举 a 和 b，令 c = n - a - b，然后判断 max - min 是否不超过 1。这样写不容易漏，也不容易把 r 的分类写错，代价只是多跑几万次判断，完全值得。枚举到合法终态后，比较它们的最小代价，取全局最小；如果某个终态的代价等于全局最小，就把它的方案数累加进答案。
这里有个坑：不要在枚举过程中“边更新最小值边清零方案数”，因为可能先遇到一个大代价终态、把答案设为它，后来遇到更小的再覆盖，逻辑上没问题；但如果写反了，先累加再更新最小值，就会把不该算的方案数算进去。稳妥的写法是两遍：第一遍找最小代价，第二遍累加等于最小代价的方案数；或者一遍但严格按“小于则覆盖、等于则累加”的顺序写。我倾向后者，代码短，但心里要清楚这个顺序不能乱。
3.3 C++ 完整实现与逐行说明
下面这版是我自己常用的写法，滚动数组加双目标合并，读入单组字符串，输出两行。
#include <bits/stdc++.h> using namespace std; static const int MOD = 51123987; static const int INF = 0x3f3f3f3f; int best[2][155][155]; int ways[2][155][155]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; if (!(cin >> s)) return 0; int n = (int)s.size(); memset(best, 0x3f, sizeof(best)); memset(ways, 0, sizeof(ways)); best[0][0][0] = 0; ways[0][0][0] = 1; for (int i = 0; i < n; ++i) { int cur = i & 1, nxt = cur ^ 1; memset(best[nxt], 0x3f, sizeof(best[nxt])); memset(ways[nxt], 0, sizeof(ways[nxt])); for (int a = 0; a <= i; ++a) { for (int b = 0; a + b <= i; ++b) { if (best[cur][a][b] == INF) continue; int c = i - a - b; int base = best[cur][a][b]; int w = ways[cur][a][b]; for (int k = 0; k < 3; ++k) { int na = a + (k == 0); int nb = b + (k == 1); int nc = c + (k == 2); if (na > n || nb > n || nc > n) continue; int cost = base + (s[i] - 'a' != k ? 1 : 0); if (cost < best[nxt][na][nb]) { best[nxt][na][nb] = cost; ways[nxt][na][nb] = w; } else if (cost == best[nxt][na][nb]) { ways[nxt][na][nb] += w; if (ways[nxt][na][nb] >= MOD) ways[nxt][na][nb] -= MOD; } } } } } int last = n & 1; int ansCost = INF, ansWays = 0; for (int a = 0; a <= n; ++a) { for (int b = 0; a + b <= n; ++b) { int c = n - a - b; int mx = max({a, b, c}); int mn = min({a, b, c}); if (mx - mn > 1) continue; if (best[last][a][b] == INF) continue; if (best[last][a][b] < ansCost) { ansCost = best[last][a][b]; ansWays = ways[last][a][b]; } else if (best[last][a][b] == ansCost) { ansWays += ways[last][a][b]; if (ansWays >= MOD) ansWays -= MOD; } } } cout << ansCost << '\n' << ansWays % MOD << '\n'; return 0; }几个关键位置的说明。第一，转移里判断s[i] - 'a' != k时，k 取 0、1、2 分别代表放 a、b、c，这个映射必须和后面的计数维一一对应，写反了会得到完全错误的代价但不一定报错。第二，na、nb、nc三个上界检查其实只有nc有可能超，因为 na 最多是 a+1 不超过 i+1，nb 同理，但加上判断更保险，也顺便表达了“计数不能超过总长度”的意思。第三，取模用的是减一次而不是取余，因为两个小于 MOD 的数相加，和一定小于 2 × MOD，减一次就够，比%快，也更不容易写错。第四，最后一层的下标是n & 1，因为第 n 次迭代写入的是nxt = (n-1)&1 ^ 1，这个值和n & 1恒等，直接用n & 1更直观。
3.4 Python 版与复杂度实测
Python 写这题我一般用字典存状态，键是 (a, b)，值是 (cost, ways)，因为字典只保存可达状态，实际规模比满表小很多，代码也更短。
MOD = 51123987 def solve(s): n = len(s) cur = {(0, 0): (0, 1)} for i, ch in enumerate(s): target = ord(ch) - 97 nxt = {} for (a, b), (cost, ways) in cur.items(): c = i - a - b for k in range(3): na = a + (1 if k == 0 else 0) nb = b + (1 if k == 1 else 0) nc = c + (1 if k == 2 else 0) if nc < 0 or nc > n or na > n or nb > n: continue add = 0 if k == target else 1 key = (na, nb) new_cost = cost + add old = nxt.get(key) if old is None or new_cost < old[0]: nxt[key] = (new_cost, ways) elif new_cost == old[0]: nxt[key] = (old[0], (old[1] + ways) % MOD) cur = nxt ans_cost, ans_ways = None, 0 for (a, b), (cost, ways) in cur.items(): c = n - a - b if max(a, b, c) - min(a, b, c) > 1: continue if ans_cost is None or cost < ans_cost: ans_cost, ans_ways = cost, ways elif cost == ans_cost: ans_ways = (ans_ways + ways) % MOD return ans_cost, ans_ways字典版本在 n = 150 时的状态数最多也就两万出头，每个状态三次转移，
