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，且当前处于蓄力状态k（0表示未蓄力，1表示已蓄力）”的方案数。这里k必须进状态，因为蓄力状态会影响下一回合的伤害计算。
转移分情况：
- 如果k=0（未蓄力）：
- 选普通攻击：
dp[i+1][j+1][0] += dp[i][j][0] - 选重击：
dp[i+1][j+3][0] += dp[i][j][0] - 选蓄力：
dp[i+1][j][1] += dp[i][j][0]
- 选普通攻击：
- 如果k=1（已蓄力）：
- 选普通攻击：伤害翻倍，
dp[i+1][j+2][0] += dp[i][j][1] - 选重击：伤害翻倍，
dp[i+1][j+6][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^9+7，两个模数以内的数相加不会超过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[i+1][...] += dp[i][...]写了两次，或者循环变量写错导致同一对(i,j)被处理了多次。
5.2 答案偏小：大概率是漏了状态或边界
如果答案比预期小，先检查边界初始化。dp[0][0]是不是1？非法状态是不是清零了？然后检查转移是否覆盖了所有可能的行动。比如蓄力状态下的转移是不是忘了写？某些伤害值是不是因为数组开小了被截断了？
还有一个隐蔽的坑：取模导致的“假零”。如果某个中间状态的真实方案数是模数的倍数，取模后变成0，后续从这个状态转移出去的全是0，但真实方案数其实不为零。这种情况在模数较小时容易出现，解决办法是换个大模数，或者用多模数验证。
5.3 运行超时：状态太多或转移太慢
计数DP的时间复杂度是“状态数 × 每个状态的转移数”。如果超时，先看能不能砍状态维度，再看能不能砍转移。砍状态的思路是“哪些信息其实不影响后续决策”，砍转移的思路是“能不能用前缀和、差分、矩阵快速幂等技巧批量处理”。
比如“666RPG”里如果伤害增量只有+1和+3，那转移可以写成dp[i+1][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[i+1][j+1][0] = (dp[i+1][j+1][0] + dp[i][j][k]) % MOD; // 重击 if (j + 3 <= MAXT) dp[i+1][j+3][0] = (dp[i+1][j+3][0] + dp[i][j][k]) % MOD; // 蓄力 dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][k]) % MOD; } else { // 蓄力后普通攻击，伤害翻倍 if (j + 2 <= MAXT) dp[i+1][j+2][0] = (dp[i+1][j+2][0] + dp[i][j][k]) % MOD; // 蓄力后重击，伤害翻倍 if (j + 6 <= MAXT) dp[i+1][j+6][0] = (dp[i+1][j+6][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][MAXT+1][2]，用i & 1和(i+1) & 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的调试利器：把中间状态的方案数打印出来，和手算的小规模样例对比。小规模样例（n=3、T=5这种）手算完全可行，对上了再跑大规模。
9. 从“666RPG”延伸出去：计数DP的通用解题框架
拿到任何一道计数DP题，我的思考顺序是这样的：
- 确定“阶段”是什么。通常是时间步、位置、处理到的元素下标。
- 确定“状态”需要哪些信息。问自己：到达这个阶段后，哪些信息会影响后续决策？只保留这些信息。
- 确定“转移”有哪些。把当前阶段所有可能的行动列出来，每个行动对应一个状态转移。
- 检查转移分类是否互斥且完备。互斥保证不算重，完备保证不算漏。
- 确定边界。起点状态方案数为1，非法状态方案数为0。
- 确定答案统计方式。是取某个特定状态，还是取一组状态的和。
- 考虑优化。状态能不能砍？转移能不能用前缀和/矩阵快速幂加速？空间能不能滚动？
这个框架适用于绝大多数计数DP题，包括“666RPG”这种带游戏背景的。背景故事只是包装，剥开后就是阶段、状态、转移三件事。
最后分享一个我个人的习惯：写完计数DP后，我一定会用一个小规模样例手算验证。比如n=3、T=5，把所有可能的行动序列列出来，数一数方案数，和程序输出对比。这个习惯帮我抓出了至少一半的计数DP bug。计数DP不像最优化DP那样有“单调性”之类的直觉可以依赖，手算验证是最可靠的。
