1. 从“666RPG”说起一个计数DP问题的完整拆解第一次看到“666RPG”这个标题很多人会以为是某款角色扮演游戏的攻略或者评测。实际上这是一道典型的计数类动态规划题目核心玩法跟游戏本身关系不大真正的主角是状态设计和转移方程。我最初接触这类题的时候也走了不少弯路觉得DP嘛无非就是写个递推但计数DP和普通的“最优解DP”在思维方式上有本质区别——它不关心“最大/最小是多少”而是关心“有多少种方案能达到目标状态”。这篇文章适合谁看如果你已经了解动态规划的基本概念比如背包、最长上升子序列但在面对“求方案数”类问题时总是拿不准状态怎么定义、边界怎么处理、会不会重复计数那这篇内容就是写给你的。我会从题目本身的逻辑出发把计数DP的通用套路、状态设计思路、转移细节、常见坑点全部拆开讲一遍最后给出一份可以直接参考的代码实现。全文基于常见的计数DP实践来补充细节不涉及任何特定平台的题目原文。先把这个问题的核心需求说清楚给定一个长度为n的操作序列每个位置可以选择若干种操作问有多少种操作方案能使得最终结果恰好等于某个目标值。这类问题的通用解法就是计数DP——用dp数组记录“到达某个状态有多少种方式”然后按顺序枚举每个位置、每种选择把方案数累加过去。听起来简单但真正写起来状态维度、取模、边界初始化、转移顺序每一个环节都可能出问题。2. 计数DP到底在数什么核心思路与方案选型2.1 计数DP和最优解DP的本质区别很多人学DP是从背包问题入门的习惯了“dp[i][j]表示前i个物品容量为j时的最大价值”这种定义。到了计数DP如果还按这个思路去想就容易卡住。原因在于最优解DP的转移是取max或min而计数DP的转移是加法原理——把所有能到达当前状态的方案数加起来。举个生活化的例子。假设你要从家到公司有3条地铁线路和2条公交线路可以选问一共有几种走法。最优解DP会告诉你“最快的那条路需要20分钟”而计数DP会告诉你“一共有5种走法”。这两者的状态定义看起来很像但转移逻辑完全不同前者是dp[i] min(dp[i-1] cost)后者是dp[i] dp[i-1] dp[i-2]这种累加形式。在“666RPG”这类问题中我们关心的就是方案总数。每一个操作步骤都可能把当前状态推向不同的新状态而我们要做的就是统计所有可能的路径数量。2.2 状态设计的核心原则计数DP的状态设计有一个铁律不重不漏。所谓“不重”就是同一种方案不能被统计两次所谓“不漏”就是所有合法方案都必须被覆盖到。这两点说起来容易做起来非常容易翻车。以“666RPG”为例如果题目中每个位置有k种操作可选每种操作会改变某个数值比如生命值、攻击力、金币数等那么最自然的状态定义就是dp[i][j]表示经过前i步操作后某个关键数值为j的方案数。这里的“关键数值”是什么取决于题目要求最终等于什么。状态维度怎么定一般来说如果只有一个目标数值需要追踪那就是二维DP步数×数值。如果有两个数值同时影响结果那就需要三维甚至更高。维度的选择直接决定了时间复杂度和空间复杂度所以能压缩的维度一定要压缩。2.3 为什么选择递推而不是记忆化搜索计数DP可以用两种方式实现递推自底向上和记忆化搜索自顶向下。在“666RPG”这类问题中我更推荐递推原因有三第一递推的转移顺序天然清晰。我们按步骤从第1步推到第n步每一步只依赖前一步的状态不会出现循环依赖的问题。第二递推方便做滚动数组优化。如果dp[i]只依赖dp[i-1]那就可以把第一维压掉空间直接从O(n×m)降到O(m)。第三递推在取模运算上更直观不容易因为递归深度导致栈溢出。当然记忆化搜索也有它的优势——对于状态转移比较复杂、不是所有状态都会被访问到的情况记忆化搜索可以避免无效计算。但在“666RPG”这种每步都要枚举所有可能操作的场景下递推的效率通常更高。3. 状态转移方程的推导与细节打磨3.1 转移方程的基本形式假设题目中有n个步骤每个步骤有若干种操作每种操作会让当前数值从x变为xcc可能是正数、负数或零目标是在n步之后数值恰好等于T。那么转移方程可以写成dp[i][j] sum(dp[i-1][j - c_k]) 对所有合法操作k其中c_k是第k种操作带来的数值变化量。这个方程的含义是到达第i步数值为j的方案数等于所有能从第i-1步的某个状态通过一步操作到达j的方案数之和。看起来很简单但实际操作中有几个关键细节需要处理。第一个是边界初始化dp[0][初始值] 1其余为0。这表示“第0步时数值为初始值的方案有1种”。第二个是取模计数DP的结果通常很大题目一般会要求对某个数取模比如1e97所以每次加法后都要取模。第三个是非法状态的处理如果某个数值超出了合理范围比如生命值不能为负那这些状态应该被跳过。3.2 数值范围的确定与偏移处理在实际写代码的时候数值可能是负数但数组下标不能为负。这时候就需要做一个偏移映射——把所有可能的数值加上一个偏移量映射到非负整数区间。比如数值范围是[-1000, 1000]那我们可以开一个大小为2001的数组下标0对应-1000下标1000对应0下标2000对应1000。每次访问数值v时实际访问的下标是v offset。这个技巧在计数DP中非常常用几乎每道题都会用到。偏移量怎么确定最稳妥的方法是先算出数值可能达到的最小值和最大值然后取offset -min_value。如果中间过程可能超出这个范围那数组就要开得更大一些。我个人的习惯是宁可多开一点空间也不要因为越界导致结果错误。3.3 滚动数组优化的正确姿势当n很大比如1e5而数值范围较小比如2000时二维数组dp[n][m]会爆内存。这时候就需要滚动数组优化——只保留当前步和上一步的状态。具体做法是开两个一维数组pre和cur每次迭代时用pre计算cur然后交换两者。代码大概长这样pre [0] * size pre[offset start] 1 for i in range(1, n 1): cur [0] * size for j in range(size): if pre[j] 0: continue for c in operations: nj j c if 0 nj size: cur[nj] (cur[nj] pre[j]) % MOD pre cur这里有一个容易忽略的优化如果pre[j] 0那就不需要枚举操作了直接跳过。这个剪枝在稀疏状态下能省不少时间。注意滚动数组优化时每一轮都要重新把cur清零。如果忘了清零上一轮的数据会污染当前轮的结果导致答案偏大。4. 完整实操流程从读题到AC的每一步4.1 第一步确定状态维度和数值范围拿到“666RPG”这类题目第一件事不是写代码而是手算一遍样例。通过样例可以确认每一步有哪些操作可选、操作对数值的影响是什么、最终目标值是多少、中间数值会不会超出某个范围。假设经过分析我们得到以下信息初始值为0共n步每步可以选择1、-1或2三种操作目标值为T数值范围在[-n, 2n]之间。那么状态就是dp[i][j]其中i从0到nj从-n到2n。数组大小是(n1) × (3n1)偏移量offset n。4.2 第二步初始化与边界处理初始化的核心是dp[0][offset 0] 1表示第0步数值为0的方案数为1。其余全部为0。这一步看起来简单但很多人会忘记初始化导致整个dp数组全是0最后输出0。边界处理主要针对两种情况一是数值超出合法范围时直接跳过二是最终答案只取dp[n][offset T]其他状态不管。4.3 第三步逐层递推与取模递推的过程就是三层循环外层枚举步数i中层枚举当前数值j内层枚举所有操作c。每次更新cur[j c] pre[j]然后取模。这里有一个性能上的小技巧如果操作种类很多可以把相同变化量的操作合并。比如1操作有3种不同的方式那实际上对方案数的贡献是pre[j] × 3而不是循环3次。这个优化在操作种类多但变化量少的时候特别有效。4.4 第四步输出答案与验证最后输出dp[n][offset T]即可。但在此之前建议用一个小样例手动验证一遍。比如n2操作是1和-1目标T0手动枚举所有4种组合(1,1)2(1,-1)0(-1,1)0(-1,-1)-2。所以答案是2。用代码跑一遍如果输出2就说明逻辑没问题。5. 常见问题与排查技巧实录5.1 答案偏大重复计数了这是计数DP最常见的问题。原因通常是转移时没有考虑“同一种方案被多次统计”。比如在枚举操作时如果两种操作实际上产生相同的效果但被当成了不同的操作来累加就会导致重复计数。解决方法仔细检查每种操作是否真的不同。如果题目说“选择一种操作”那不同操作即使效果相同也应该算不同方案如果题目说“选择一种效果”那相同效果的操作应该合并。5.2 答案偏小漏掉了某些状态漏状态的原因通常有两个一是数值范围开小了某些中间状态被截断二是初始化不完整某些起始状态没有赋值为1。排查方法把dp数组中间过程打印出来看看哪些状态是0但理论上不应该为0。另外检查偏移量是否足够大确保所有可能的数值都能映射到合法下标。5.3 运行超时循环层数太多如果n和数值范围都很大三层循环可能会超时。优化方向有三个一是滚动数组减少空间间接提升缓存命中率二是合并相同变化量的操作三是如果转移方程有规律可以考虑用前缀和优化。比如如果操作是“数值增加1到k之间的任意值”那转移方程可以写成dp[i][j] sum(dp[i-1][j-1] ... dp[i-1][j-k])这个可以用前缀和优化到O(1)转移。5.4 取模相关的坑取模运算有三个注意点第一每次加法后都要取模不要等到最后才取否则中间结果可能溢出第二如果涉及减法要加上MOD再取模避免出现负数第三MOD通常是质数但计数DP一般不需要逆元直接用加法取模即可。问题现象可能原因排查方法答案偏大重复计数检查操作是否被重复枚举答案偏小状态遗漏打印中间dp数组检查0状态运行超时循环过多滚动数组、合并操作、前缀和结果为负减法未处理加MOD后再取模数组越界偏移不足扩大数组范围或调整offset实操心得写计数DP的时候我习惯先写一个暴力搜索版本用小数据对拍。暴力搜索虽然慢但逻辑简单不容易错用它来验证DP的正确性非常有效。6. 从“666RPG”延伸计数DP的通用套路6.1 计数DP的识别特征什么样的题目应该用计数DP一般来说题目中出现“有多少种方案”、“求方案数”、“有多少种不同的走法”这类表述时基本就是计数DP。另外如果题目要求“输出答案对1e97取模”那几乎可以确定是计数类问题。和最优解DP相比计数DP的转移方程更“对称”——它不涉及max/min的比较而是纯粹的加法。这使得计数DP在某些情况下可以用矩阵快速幂来加速但那是另一个话题了。6.2 状态压缩的常见手法当状态维度太高时可以考虑状态压缩。比如如果两个数值之和是固定的那只需要记录其中一个另一个可以通过总和减去它得到。再比如如果某些状态永远不会被访问到可以用哈希表来代替数组只存有效状态。在“666RPG”中如果操作只涉及加法且所有操作都是正数那数值是单调递增的很多状态其实不会出现。这时候用字典来存状态比用数组更省空间。6.3 计数DP与其他DP技巧的结合计数DP经常和其他DP技巧结合使用。比如计数DP 背包求恰好装满背包的方案数计数DP 树形DP求树上满足条件的路径条数计数DP 数位DP求区间内满足条件的数字个数计数DP 状压DP求覆盖棋盘的所有方案数这些组合本质上都是“在某种状态空间上做方案计数”核心思想是一致的。7. 代码实现参考与逐行注释下面给出一份完整的Python实现对应“666RPG”的通用场景。假设有n步每步可以执行operations中的任意一种操作每种操作对数值的影响是operations[k]初始值为start目标值为target所有结果对MOD取模。MOD 10**9 7 def solve(n, operations, start, target): # 确定数值范围 min_val start sum(min(0, c) for c in operations) * n max_val start sum(max(0, c) for c in operations) * n offset -min_val size max_val - min_val 1 # 初始化 pre [0] * size pre[offset start] 1 # 逐层递推 for i in range(1, n 1): cur [0] * size for j in range(size): if pre[j] 0: continue for c in operations: nj j c if 0 nj size: cur[nj] (cur[nj] pre[j]) % MOD pre cur # 输出答案 idx offset target if 0 idx size: return pre[idx] return 0这份代码的时间复杂度是O(n × size × k)其中k是操作种类数。如果size和k都不大这个复杂度是可以接受的。如果n很大但size较小可以考虑用矩阵快速幂进一步优化。提示在实际写题的时候数组大小建议比理论范围多开10%到20%防止边界情况越界。这个习惯帮我省了很多调试时间。8. 一些踩过的坑和实战建议计数DP看起来简单但真正写起来坑不少。我印象最深的一次是有一道题我死活过不了样例后来发现是初始化的时候把dp[0][start]写成了dp[0][0]而start并不是0。这种低级错误在紧张比赛的时候特别容易犯。另一个常见的坑是取模的时机。有一次我为了省事只在最后输出的时候取模结果中间结果太大导致整数溢出答案完全不对。后来改成每次加法后立即取模问题就解决了。还有一次是滚动数组忘记清零cur导致上一轮的数据混进来答案偏大了一倍多。这个bug我找了快半个小时才定位到因为逻辑上看起来完全没问题但就是结果不对。实战建议的话我觉得有几点特别重要第一先用小数据暴力对拍确认DP逻辑正确后再优化第二数组大小宁可多开不要少开第三取模要勤快不要偷懒第四滚动数组记得清零第五偏移量算清楚不要凭感觉。这类计数DP题目在各类算法练习中出现的频率很高掌握之后可以延伸到很多变种问题。比如把线性结构换成树形结构就变成了树形计数DP把数值范围换成二进制位就变成了数位计数DP。核心思想都是一样的——定义好状态想清楚转移注意不重不漏。 
长河君 · 2026/10/9 21:51:34 · 阅读 1.2k 计数DP实战：从666RPG拆解状态设计与转移方程
1. 从“666RPG”说起一个计数DP问题的完整拆解第一次看到“666RPG”这个标题很多人会以为是某款角色扮演游戏的攻略或者评测。实际上这是一道典型的计数类动态规划题目核心玩法跟游戏本身关系不大真正的主角是状态设计和转移方程。我最初接触这类题的时候也走了不少弯路觉得DP嘛无非就是写个递推但计数DP和普通的“最优解DP”在思维方式上有本质区别——它不关心“最大/最小是多少”而是关心“有多少种方案能达到目标状态”。这篇文章适合谁看如果你已经了解动态规划的基本概念比如背包、最长上升子序列但在面对“求方案数”类问题时总是拿不准状态怎么定义、边界怎么处理、会不会重复计数那这篇内容就是写给你的。我会从题目本身的逻辑出发把计数DP的通用套路、状态设计思路、转移细节、常见坑点全部拆开讲一遍最后给出一份可以直接参考的代码实现。全文基于常见的计数DP实践来补充细节不涉及任何特定平台的题目原文。先把这个问题的核心需求说清楚给定一个长度为n的操作序列每个位置可以选择若干种操作问有多少种操作方案能使得最终结果恰好等于某个目标值。这类问题的通用解法就是计数DP——用dp数组记录“到达某个状态有多少种方式”然后按顺序枚举每个位置、每种选择把方案数累加过去。听起来简单但真正写起来状态维度、取模、边界初始化、转移顺序每一个环节都可能出问题。2. 计数DP到底在数什么核心思路与方案选型2.1 计数DP和最优解DP的本质区别很多人学DP是从背包问题入门的习惯了“dp[i][j]表示前i个物品容量为j时的最大价值”这种定义。到了计数DP如果还按这个思路去想就容易卡住。原因在于最优解DP的转移是取max或min而计数DP的转移是加法原理——把所有能到达当前状态的方案数加起来。举个生活化的例子。假设你要从家到公司有3条地铁线路和2条公交线路可以选问一共有几种走法。最优解DP会告诉你“最快的那条路需要20分钟”而计数DP会告诉你“一共有5种走法”。这两者的状态定义看起来很像但转移逻辑完全不同前者是dp[i] min(dp[i-1] cost)后者是dp[i] dp[i-1] dp[i-2]这种累加形式。在“666RPG”这类问题中我们关心的就是方案总数。每一个操作步骤都可能把当前状态推向不同的新状态而我们要做的就是统计所有可能的路径数量。2.2 状态设计的核心原则计数DP的状态设计有一个铁律不重不漏。所谓“不重”就是同一种方案不能被统计两次所谓“不漏”就是所有合法方案都必须被覆盖到。这两点说起来容易做起来非常容易翻车。以“666RPG”为例如果题目中每个位置有k种操作可选每种操作会改变某个数值比如生命值、攻击力、金币数等那么最自然的状态定义就是dp[i][j]表示经过前i步操作后某个关键数值为j的方案数。这里的“关键数值”是什么取决于题目要求最终等于什么。状态维度怎么定一般来说如果只有一个目标数值需要追踪那就是二维DP步数×数值。如果有两个数值同时影响结果那就需要三维甚至更高。维度的选择直接决定了时间复杂度和空间复杂度所以能压缩的维度一定要压缩。2.3 为什么选择递推而不是记忆化搜索计数DP可以用两种方式实现递推自底向上和记忆化搜索自顶向下。在“666RPG”这类问题中我更推荐递推原因有三第一递推的转移顺序天然清晰。我们按步骤从第1步推到第n步每一步只依赖前一步的状态不会出现循环依赖的问题。第二递推方便做滚动数组优化。如果dp[i]只依赖dp[i-1]那就可以把第一维压掉空间直接从O(n×m)降到O(m)。第三递推在取模运算上更直观不容易因为递归深度导致栈溢出。当然记忆化搜索也有它的优势——对于状态转移比较复杂、不是所有状态都会被访问到的情况记忆化搜索可以避免无效计算。但在“666RPG”这种每步都要枚举所有可能操作的场景下递推的效率通常更高。3. 状态转移方程的推导与细节打磨3.1 转移方程的基本形式假设题目中有n个步骤每个步骤有若干种操作每种操作会让当前数值从x变为xcc可能是正数、负数或零目标是在n步之后数值恰好等于T。那么转移方程可以写成dp[i][j] sum(dp[i-1][j - c_k]) 对所有合法操作k其中c_k是第k种操作带来的数值变化量。这个方程的含义是到达第i步数值为j的方案数等于所有能从第i-1步的某个状态通过一步操作到达j的方案数之和。看起来很简单但实际操作中有几个关键细节需要处理。第一个是边界初始化dp[0][初始值] 1其余为0。这表示“第0步时数值为初始值的方案有1种”。第二个是取模计数DP的结果通常很大题目一般会要求对某个数取模比如1e97所以每次加法后都要取模。第三个是非法状态的处理如果某个数值超出了合理范围比如生命值不能为负那这些状态应该被跳过。3.2 数值范围的确定与偏移处理在实际写代码的时候数值可能是负数但数组下标不能为负。这时候就需要做一个偏移映射——把所有可能的数值加上一个偏移量映射到非负整数区间。比如数值范围是[-1000, 1000]那我们可以开一个大小为2001的数组下标0对应-1000下标1000对应0下标2000对应1000。每次访问数值v时实际访问的下标是v offset。这个技巧在计数DP中非常常用几乎每道题都会用到。偏移量怎么确定最稳妥的方法是先算出数值可能达到的最小值和最大值然后取offset -min_value。如果中间过程可能超出这个范围那数组就要开得更大一些。我个人的习惯是宁可多开一点空间也不要因为越界导致结果错误。3.3 滚动数组优化的正确姿势当n很大比如1e5而数值范围较小比如2000时二维数组dp[n][m]会爆内存。这时候就需要滚动数组优化——只保留当前步和上一步的状态。具体做法是开两个一维数组pre和cur每次迭代时用pre计算cur然后交换两者。代码大概长这样pre [0] * size pre[offset start] 1 for i in range(1, n 1): cur [0] * size for j in range(size): if pre[j] 0: continue for c in operations: nj j c if 0 nj size: cur[nj] (cur[nj] pre[j]) % MOD pre cur这里有一个容易忽略的优化如果pre[j] 0那就不需要枚举操作了直接跳过。这个剪枝在稀疏状态下能省不少时间。注意滚动数组优化时每一轮都要重新把cur清零。如果忘了清零上一轮的数据会污染当前轮的结果导致答案偏大。4. 完整实操流程从读题到AC的每一步4.1 第一步确定状态维度和数值范围拿到“666RPG”这类题目第一件事不是写代码而是手算一遍样例。通过样例可以确认每一步有哪些操作可选、操作对数值的影响是什么、最终目标值是多少、中间数值会不会超出某个范围。假设经过分析我们得到以下信息初始值为0共n步每步可以选择1、-1或2三种操作目标值为T数值范围在[-n, 2n]之间。那么状态就是dp[i][j]其中i从0到nj从-n到2n。数组大小是(n1) × (3n1)偏移量offset n。4.2 第二步初始化与边界处理初始化的核心是dp[0][offset 0] 1表示第0步数值为0的方案数为1。其余全部为0。这一步看起来简单但很多人会忘记初始化导致整个dp数组全是0最后输出0。边界处理主要针对两种情况一是数值超出合法范围时直接跳过二是最终答案只取dp[n][offset T]其他状态不管。4.3 第三步逐层递推与取模递推的过程就是三层循环外层枚举步数i中层枚举当前数值j内层枚举所有操作c。每次更新cur[j c] pre[j]然后取模。这里有一个性能上的小技巧如果操作种类很多可以把相同变化量的操作合并。比如1操作有3种不同的方式那实际上对方案数的贡献是pre[j] × 3而不是循环3次。这个优化在操作种类多但变化量少的时候特别有效。4.4 第四步输出答案与验证最后输出dp[n][offset T]即可。但在此之前建议用一个小样例手动验证一遍。比如n2操作是1和-1目标T0手动枚举所有4种组合(1,1)2(1,-1)0(-1,1)0(-1,-1)-2。所以答案是2。用代码跑一遍如果输出2就说明逻辑没问题。5. 常见问题与排查技巧实录5.1 答案偏大重复计数了这是计数DP最常见的问题。原因通常是转移时没有考虑“同一种方案被多次统计”。比如在枚举操作时如果两种操作实际上产生相同的效果但被当成了不同的操作来累加就会导致重复计数。解决方法仔细检查每种操作是否真的不同。如果题目说“选择一种操作”那不同操作即使效果相同也应该算不同方案如果题目说“选择一种效果”那相同效果的操作应该合并。5.2 答案偏小漏掉了某些状态漏状态的原因通常有两个一是数值范围开小了某些中间状态被截断二是初始化不完整某些起始状态没有赋值为1。排查方法把dp数组中间过程打印出来看看哪些状态是0但理论上不应该为0。另外检查偏移量是否足够大确保所有可能的数值都能映射到合法下标。5.3 运行超时循环层数太多如果n和数值范围都很大三层循环可能会超时。优化方向有三个一是滚动数组减少空间间接提升缓存命中率二是合并相同变化量的操作三是如果转移方程有规律可以考虑用前缀和优化。比如如果操作是“数值增加1到k之间的任意值”那转移方程可以写成dp[i][j] sum(dp[i-1][j-1] ... dp[i-1][j-k])这个可以用前缀和优化到O(1)转移。5.4 取模相关的坑取模运算有三个注意点第一每次加法后都要取模不要等到最后才取否则中间结果可能溢出第二如果涉及减法要加上MOD再取模避免出现负数第三MOD通常是质数但计数DP一般不需要逆元直接用加法取模即可。问题现象可能原因排查方法答案偏大重复计数检查操作是否被重复枚举答案偏小状态遗漏打印中间dp数组检查0状态运行超时循环过多滚动数组、合并操作、前缀和结果为负减法未处理加MOD后再取模数组越界偏移不足扩大数组范围或调整offset实操心得写计数DP的时候我习惯先写一个暴力搜索版本用小数据对拍。暴力搜索虽然慢但逻辑简单不容易错用它来验证DP的正确性非常有效。6. 从“666RPG”延伸计数DP的通用套路6.1 计数DP的识别特征什么样的题目应该用计数DP一般来说题目中出现“有多少种方案”、“求方案数”、“有多少种不同的走法”这类表述时基本就是计数DP。另外如果题目要求“输出答案对1e97取模”那几乎可以确定是计数类问题。和最优解DP相比计数DP的转移方程更“对称”——它不涉及max/min的比较而是纯粹的加法。这使得计数DP在某些情况下可以用矩阵快速幂来加速但那是另一个话题了。6.2 状态压缩的常见手法当状态维度太高时可以考虑状态压缩。比如如果两个数值之和是固定的那只需要记录其中一个另一个可以通过总和减去它得到。再比如如果某些状态永远不会被访问到可以用哈希表来代替数组只存有效状态。在“666RPG”中如果操作只涉及加法且所有操作都是正数那数值是单调递增的很多状态其实不会出现。这时候用字典来存状态比用数组更省空间。6.3 计数DP与其他DP技巧的结合计数DP经常和其他DP技巧结合使用。比如计数DP 背包求恰好装满背包的方案数计数DP 树形DP求树上满足条件的路径条数计数DP 数位DP求区间内满足条件的数字个数计数DP 状压DP求覆盖棋盘的所有方案数这些组合本质上都是“在某种状态空间上做方案计数”核心思想是一致的。7. 代码实现参考与逐行注释下面给出一份完整的Python实现对应“666RPG”的通用场景。假设有n步每步可以执行operations中的任意一种操作每种操作对数值的影响是operations[k]初始值为start目标值为target所有结果对MOD取模。MOD 10**9 7 def solve(n, operations, start, target): # 确定数值范围 min_val start sum(min(0, c) for c in operations) * n max_val start sum(max(0, c) for c in operations) * n offset -min_val size max_val - min_val 1 # 初始化 pre [0] * size pre[offset start] 1 # 逐层递推 for i in range(1, n 1): cur [0] * size for j in range(size): if pre[j] 0: continue for c in operations: nj j c if 0 nj size: cur[nj] (cur[nj] pre[j]) % MOD pre cur # 输出答案 idx offset target if 0 idx size: return pre[idx] return 0这份代码的时间复杂度是O(n × size × k)其中k是操作种类数。如果size和k都不大这个复杂度是可以接受的。如果n很大但size较小可以考虑用矩阵快速幂进一步优化。提示在实际写题的时候数组大小建议比理论范围多开10%到20%防止边界情况越界。这个习惯帮我省了很多调试时间。8. 一些踩过的坑和实战建议计数DP看起来简单但真正写起来坑不少。我印象最深的一次是有一道题我死活过不了样例后来发现是初始化的时候把dp[0][start]写成了dp[0][0]而start并不是0。这种低级错误在紧张比赛的时候特别容易犯。另一个常见的坑是取模的时机。有一次我为了省事只在最后输出的时候取模结果中间结果太大导致整数溢出答案完全不对。后来改成每次加法后立即取模问题就解决了。还有一次是滚动数组忘记清零cur导致上一轮的数据混进来答案偏大了一倍多。这个bug我找了快半个小时才定位到因为逻辑上看起来完全没问题但就是结果不对。实战建议的话我觉得有几点特别重要第一先用小数据暴力对拍确认DP逻辑正确后再优化第二数组大小宁可多开不要少开第三取模要勤快不要偷懒第四滚动数组记得清零第五偏移量算清楚不要凭感觉。这类计数DP题目在各类算法练习中出现的频率很高掌握之后可以延伸到很多变种问题。比如把线性结构换成树形结构就变成了树形计数DP把数值范围换成二进制位就变成了数位计数DP。核心思想都是一样的——定义好状态想清楚转移注意不重不漏。