1. 从“666RPG”这个标题说起计数DP到底在算什么第一次看到“666RPG计数dp”这个标题很多人会愣一下RPG不是角色扮演游戏吗怎么跟DP扯上关系了其实这里的RPG并不是指游戏类型而是题目背景里常见的“角色扮演”外壳——给你一个角色有若干属性、若干行动、若干限制条件问你有多少种方式能让角色达成某个目标。剥掉这层故事外衣内核就是一道计数类动态规划题。计数DP和最常见的“最优化DP”求最大价值、最小代价是两条路子。最优化DP的状态转移通常写dp[i] max(dp[i-1], dp[i-2] a[i])取的是极值而计数DP的状态转移是加法原理dp[i] dp[i-1] dp[i-2]累加的是方案数。这个区别看起来很小但在实际写题时踩的坑完全不一样最优化DP你担心的是“漏掉更优解”计数DP你担心的是“算重了”或者“算漏了”。“666”这个词在题目里通常是个数值约束或者目标值比如“凑出总和为666”“达到666点伤害”“走666步”之类。它给了一个明确的、有限的、可枚举的目标这正是计数DP最擅长的场景——目标有限、状态可定义、转移可穷举。这篇文章适合谁看如果你已经会写最简单的01背包、爬楼梯那种线性DP但一遇到“求方案数”就心里没底或者写出来的转移方程总是差那么一点那这篇就是写给你的。我会从状态定义、转移设计、边界处理、去重技巧几个层面把计数DP的完整思考链路拆开讲最后给一份可以直接照着写的模板和排查清单。2. 计数DP的核心设计思路状态、转移、边界三件套2.1 为什么计数DP的状态定义比最优化DP更“娇气”最优化DP的状态定义相对宽容。比如dp[i]表示“前i个物品能获得的最大价值”这个定义很自然因为最大值具有最优子结构你怎么定义只要保证不遗漏最优解就行。但计数DP不行计数DP的状态定义必须不重不漏一旦状态之间有重叠方案数就会偏大一旦状态覆盖不全方案数就会偏小。拿“666RPG”这类题来说假设题目是角色有初始血量每回合可以选择攻击、防御、回血三种行动问恰好经过n回合后总伤害达到666的方案数。这里的状态就不能简单定义成dp[i]表示“i回合后伤害为666的方案数”因为你还得知道当前血量是多少——血量会影响后续能不能继续攻击。所以状态至少是二维的dp[i][j]表示“i回合后当前伤害为j的方案数”。如果血量也影响转移那就得三维。计数DP的状态维度取决于“哪些信息会影响后续转移”。凡是会影响未来决策的量都必须进状态不影响未来决策的量坚决不进状态否则状态爆炸。2.2 转移方程的加法原理与“分类不重叠”原则计数DP的转移本质是分类加法把“到达状态S的所有方案”按照“最后一步做了什么”分成若干互不重叠的类别每类的方案数相加。以爬楼梯的计数版本为例dp[i] dp[i-1] dp[i-2]含义是“到达第i阶的方案 最后一步走1阶的方案 最后一步走2阶的方案”。这两类互不重叠最后一步步长不同且覆盖全部最后一步只能是1或2所以可以直接相加。在“666RPG”场景里如果最后一步可以是“普通攻击造成a点伤害”或“技能攻击造成b点伤害”那转移就是dp[i][j] dp[i-1][j-a] dp[i-1][j-b]。但这里有个陷阱如果a和b相等或者技能攻击本身也包含普通攻击的效果那两类就重叠了直接相加会算重。这时候要么把分类标准改得更细要么用容斥减去重叠部分。2.3 边界条件计数DP最容易翻车的地方最优化DP的边界写错了顶多答案偏一点计数DP的边界写错了答案可能直接差一个数量级。计数DP的边界通常有两类起点边界dp[0][0] 1表示“什么都没做、伤害为0”有1种方案空方案。这个1不能省省了后面全是0。非法状态边界伤害为负、血量小于等于0、步数超限等状态方案数直接置0且不参与转移。我见过太多人把dp[0][0]初始化成0然后纳闷为什么答案全是0。也见过人忘了把非法状态清零导致负数下标被访问或者方案数从非法路径渗透进来。3. 从零推导“666RPG”的完整转移过程3.1 把题目翻译成状态和转移的形式化描述假设题目完整描述是这样的基于常见计数DP题型的合理补全角色初始伤害为0每回合可以选择三种行动之一——普通攻击伤害1、重击伤害3、蓄力伤害不变但下回合伤害翻倍。问恰好n回合后总伤害恰好为666的方案数结果对一个大质数取模。先确定状态dp[i][j][k]表示“i回合后当前伤害为j且当前处于蓄力状态k0表示未蓄力1表示已蓄力”的方案数。这里k必须进状态因为蓄力状态会影响下一回合的伤害计算。转移分情况如果k0未蓄力选普通攻击dp[i1][j1][0] dp[i][j][0]选重击dp[i1][j3][0] dp[i][j][0]选蓄力dp[i1][j][1] dp[i][j][0]如果k1已蓄力选普通攻击伤害翻倍dp[i1][j2][0] dp[i][j][1]选重击伤害翻倍dp[i1][j6][0] dp[i][j][1]选蓄力不能连续蓄力否则无限叠所以这个转移非法或者按题目规则处理。3.2 参数计算为什么伤害上限要卡在666而不是更大状态里的j如果无脑开到很大空间和时间都会爆。这里有个关键观察伤害只会增加不会减少蓄力不改变伤害只是改变后续增量。所以一旦j超过666后续再怎么加也不可能回到666这些状态可以直接丢弃。因此j的上限就是666。如果n最大是1000那状态总数是1000 * 667 * 2 ≈ 1.3M完全在可接受范围内。如果n更大比如10^5那就得考虑用矩阵快速幂或者生成函数优化但那是另一个话题了。计数DP里“剪掉不可能到达目标的状态”是最有效的优化手段。先想清楚哪些状态是“死路”然后在转移时直接跳过能省掉大量无效计算。3.3 取模的时机与负数处理计数DP的答案通常很大必须取模。取模的时机有两个选择每次加法后取模或者用long long累加、最后统一取模。前者安全但稍慢后者快但要注意溢出。我的习惯是如果模数在10^9级别用long long累加每加几次就取一次模避免溢出。如果模数是10^97两个模数以内的数相加不会超过2*10^9在int范围内其实也安全但为了保险还是用long long。负数处理是另一个坑。如果转移里有减法比如容斥(a - b) % mod在C里可能是负数必须写成(a - b mod) % mod。这个细节在计数DP里出现频率极高尤其是涉及“减去不合法方案”的时候。4. 计数DP的常见变体与“666RPG”的扩展方向4.1 带限制条件的计数某些行动不能连续使用如果题目加一条限制“重击不能连续使用”那状态里就得再加一维表示“上一回合用了什么行动”。这就是计数DP状态维度膨胀的典型原因——每加一条“与历史相关的限制”就得多一维状态。处理这类限制的通用套路是把“上一回合的行动类型”编码进状态。比如用0表示上回合没用重击1表示上回合用了重击。转移时根据当前状态决定哪些行动可选。4.2 目标值可变的计数从666扩展到任意T如果题目不是固定666而是给一个T问达到T的方案数那状态里的j上限就是T。这时候如果T很大比如10^9就不能用数组存了得用map或者离散化或者找生成函数的封闭形式。但在“666RPG”这个具体标题下666是个固定的小目标数组完全够用。4.3 多角色或多维属性的计数如果RPG里有多个角色或者角色有多个属性攻击、防御、血量同时需要满足条件那状态就是多维的。多维计数DP的写法是嵌套循环但要注意循环顺序外层循环阶段回合数内层循环状态维度。顺序反了会导致同一阶段的状态互相转移算出来的方案数是错的。5. 实操排查清单计数DP写挂了怎么查5.1 答案偏大大概率是算重了如果答案比预期大先检查转移分类是否有重叠。比如“普通攻击”和“技能攻击”如果技能攻击的描述里包含了普通攻击的效果那这两类就重叠了。解决办法是把分类标准改成交互排斥的或者用容斥减去重叠部分。另一个常见原因是同一状态被多次累加。比如在多重循环里dp[i1][...] dp[i][...]写了两次或者循环变量写错导致同一对(i,j)被处理了多次。5.2 答案偏小大概率是漏了状态或边界如果答案比预期小先检查边界初始化。dp[0][0]是不是1非法状态是不是清零了然后检查转移是否覆盖了所有可能的行动。比如蓄力状态下的转移是不是忘了写某些伤害值是不是因为数组开小了被截断了还有一个隐蔽的坑取模导致的“假零”。如果某个中间状态的真实方案数是模数的倍数取模后变成0后续从这个状态转移出去的全是0但真实方案数其实不为零。这种情况在模数较小时容易出现解决办法是换个大模数或者用多模数验证。5.3 运行超时状态太多或转移太慢计数DP的时间复杂度是“状态数 × 每个状态的转移数”。如果超时先看能不能砍状态维度再看能不能砍转移。砍状态的思路是“哪些信息其实不影响后续决策”砍转移的思路是“能不能用前缀和、差分、矩阵快速幂等技巧批量处理”。比如“666RPG”里如果伤害增量只有1和3那转移可以写成dp[i1][j] dp[i][j-1] dp[i][j-3]用滚动数组优化空间用前缀和优化时间。症状可能原因排查方法答案偏大转移分类重叠检查每类是否互斥答案偏大同一状态重复累加打印中间状态方案数对比答案偏小边界未初始化检查dp[0][0]是否为1答案偏小非法状态未清零检查负数下标和越界答案偏小取模假零换大模数或多模数验证超时状态维度太多砍掉不影响后续的维度超时转移太慢用前缀和/矩阵快速幂优化6. 一份可以直接套用的计数DP代码模板6.1 模板结构说明下面这份模板以“666RPG”为背景但结构是通用的。你只需要替换状态维度、转移规则和目标值就能套到其他计数DP题上。#include bits/stdc.h using namespace std; const int MOD 1e9 7; const int MAXN 1005; // 最大回合数 const int MAXT 666; // 目标伤害值 int dp[MAXN][MAXT 1][2]; // dp[i][j][k]: i回合后伤害为j且蓄力状态为k的方案数 int main() { int n; cin n; // 边界初始化 dp[0][0][0] 1; for (int i 0; i n; i) { for (int j 0; j MAXT; j) { for (int k 0; k 2; k) { if (dp[i][j][k] 0) continue; if (k 0) { // 普通攻击 if (j 1 MAXT) dp[i1][j1][0] (dp[i1][j1][0] dp[i][j][k]) % MOD; // 重击 if (j 3 MAXT) dp[i1][j3][0] (dp[i1][j3][0] dp[i][j][k]) % MOD; // 蓄力 dp[i1][j][1] (dp[i1][j][1] dp[i][j][k]) % MOD; } else { // 蓄力后普通攻击伤害翻倍 if (j 2 MAXT) dp[i1][j2][0] (dp[i1][j2][0] dp[i][j][k]) % MOD; // 蓄力后重击伤害翻倍 if (j 6 MAXT) dp[i1][j6][0] (dp[i1][j6][0] dp[i][j][k]) % MOD; } } } } int ans 0; for (int k 0; k 2; k) { ans (ans dp[n][MAXT][k]) % MOD; } cout ans endl; return 0; }6.2 模板使用要点这份模板有几个地方值得注意。第一if (dp[i][j][k] 0) continue;这行剪枝在计数DP里非常关键因为大量状态其实是0跳过它们能省很多时间。第二每次加法后立即取模避免溢出。第三目标值MAXT作为数组维度所有越界的转移直接跳过保证不访问非法内存。如果你要改成“恰好T”而不是“至少T”那最后统计答案时只取dp[n][T][k]如果是“至少T”那就把dp[n][T..MAXT][k]全部加起来。这个区别在题目描述里一定要看清楚。6.3 空间优化滚动数组如果n很大但状态维度不高可以用滚动数组把第一维压掉。比如dp[2][MAXT1][2]用i 1和(i1) 1来交替。但要注意滚动数组要求当前阶段只依赖上一阶段如果转移里有跨阶段的依赖比如依赖前两阶段那就得开更大的滚动窗口。7. 计数DP与其他DP变体的关系7.1 计数DP vs 概率DP概率DP和计数DP长得很像转移都是加法但概率DP的“加法”是加权加法乘概率而且概率DP通常要求所有方案的概率之和为1。计数DP只关心方案数不关心概率。如果你把计数DP的转移直接套到概率DP上忘了乘概率答案就错了。7.2 计数DP vs 数位DP数位DP本质上也是一种计数DP只不过状态里多了“当前位”“是否贴着上界”“是否有前导零”这些维度。数位DP的计数对象是“满足数位限制的数字个数”而“666RPG”的计数对象是“满足行动序列限制的方案数”。两者的核心思想一致定义不重不漏的状态按位/按阶段转移。7.3 计数DP vs 树形DP树形DP里的计数问题比如“有多少种染色方案”也是计数DP只不过转移发生在树上通常用DFS后序遍历来合并子树信息。树形计数DP的难点在于合并两个子树时方案数要相乘乘法原理而不是相加。这个“加法还是乘法”的判断是计数DP的核心分水岭。8. 我在实际写计数DP时踩过的几个坑第一个坑是状态定义里混入了不必要的维度。有一次我写一道计数题把“当前用了几个技能”也放进状态结果状态数直接爆炸。后来发现那个信息根本不影响后续转移纯属多余。计数DP的状态维度要抠得很死每加一维都要问自己“这维真的会影响未来决策吗”。第二个坑是边界初始化时忘了空方案。dp[0][0] 1这个1代表“什么都不做的方案有一种”很多人直觉上觉得“什么都没做怎么算一种方案”就把它设成0然后全盘皆输。空方案在计数DP里是合法的而且是必须的。第三个坑是取模后比较大小。有时候我想判断“某个状态的方案数是否大于0”但取模后可能变成0导致误判。解决办法是另开一个bool数组记录“该状态是否可达”或者用多模数交叉验证。第四个坑是循环顺序写反。计数DP如果是多维的循环顺序必须保证“当前阶段只依赖已完成计算的阶段”。如果把状态维放在外层、阶段维放在内层就会出现同一阶段内互相转移方案数直接翻倍。计数DP的调试利器把中间状态的方案数打印出来和手算的小规模样例对比。小规模样例n3、T5这种手算完全可行对上了再跑大规模。9. 从“666RPG”延伸出去计数DP的通用解题框架拿到任何一道计数DP题我的思考顺序是这样的确定“阶段”是什么。通常是时间步、位置、处理到的元素下标。确定“状态”需要哪些信息。问自己到达这个阶段后哪些信息会影响后续决策只保留这些信息。确定“转移”有哪些。把当前阶段所有可能的行动列出来每个行动对应一个状态转移。检查转移分类是否互斥且完备。互斥保证不算重完备保证不算漏。确定边界。起点状态方案数为1非法状态方案数为0。确定答案统计方式。是取某个特定状态还是取一组状态的和。考虑优化。状态能不能砍转移能不能用前缀和/矩阵快速幂加速空间能不能滚动这个框架适用于绝大多数计数DP题包括“666RPG”这种带游戏背景的。背景故事只是包装剥开后就是阶段、状态、转移三件事。最后分享一个我个人的习惯写完计数DP后我一定会用一个小规模样例手算验证。比如n3、T5把所有可能的行动序列列出来数一数方案数和程序输出对比。这个习惯帮我抓出了至少一半的计数DP bug。计数DP不像最优化DP那样有“单调性”之类的直觉可以依赖手算验证是最可靠的。