1. 从一道题看数位DP的核心思想1.1 这道题到底在问什么先把这个题目的意思说清楚。所谓平衡数指的是这样一个数字存在某一个位置作为支点使得支点左边的每一位数字乘以它到支点的距离之和等于支点右边每一位数字乘以它到支点的距离之和。说白了就是拿数字的某一位当跷跷板的支点左右两边的“力矩”相等。举个例子数字4139。我们选3这个位置当支点。左边是4和14距离支点2位1距离支点1位所以左边力矩是4×2 1×1 9。右边是9距离支点1位右边力矩是9×1 9。两边相等所以4139是一个平衡数。再比如数字10选1当支点左边没有数字力矩为0右边是0距离1位力矩为0×1 0两边相等所以10也是平衡数。注意0本身也是平衡数这个边界要特别处理。题目一般会给定一个区间[L, R]问这个区间内有多少个平衡数。R的范围可能到10^18甚至更大暴力枚举肯定不行必须用数位DP。1.2 为什么这题是数位DP的经典入门数位DP的核心场景就是统计在某个区间内满足某种“与数字每一位相关”的性质的数的个数。这题完美符合这个特征——平衡性依赖于每一位数字和它到支点的距离是典型的逐位决策问题。我当初学数位DP的时候最先接触的就是这类题。它的好处在于状态设计不算太复杂但又足够让你理解数位DP的几个关键点支点枚举、前导零处理、力矩的表示、以及记忆化搜索的写法。把这题吃透后面遇到更复杂的数位DP比如统计满足某些数位和条件的数、带模数的数位统计等都能触类旁通。1.3 暴力为什么不可行假设R 10^18暴力枚举每个数再逐位判断时间复杂度是O(R × 位数)大概是10^18 × 19次操作这个量级任何计算机都跑不完。就算是区间长度小一点比如10^9也基本要跑好几秒甚至超时。所以必须找到一种方法利用数字的“位”结构来压缩状态。数位DP的本质就是把“从0到N”的枚举转化成对每一位的决策并用记忆化避免重复计算。对于平衡数这题我们枚举支点位置然后从高位到低位逐位填数字同时维护当前的力矩差值最后看差值是否为零。2. 状态设计与转移方程的推导2.1 支点枚举的必要性平衡数的定义里支点位置是不确定的。一个数可能有多个支点也可能没有。比如0有无数个支点因为两边都是0但通常我们只统计一次。最直接的想法是枚举支点位置。对于一个最多有len位的数支点可能在第1位到第len位。我们固定支点然后统计在这个支点下满足力矩平衡的数的个数。最后把所有支点的结果加起来再减去重复计数的部分。这里有个关键点一个数如果有多个支点会被重复统计。但实际上除了0以外一个数最多只有一个支点。这个结论可以简单证明假设有两个不同的支点那么两个支点之间的力矩关系会导致矛盾。所以除了0其他数最多贡献一次。0比较特殊它在每个支点下都被统计了一次所以最后要减去(len - 1)次多余的0。2.2 力矩差值的状态表示固定支点后我们需要在逐位填数的过程中维护一个“力矩差”。具体来说如果当前填到第pos位从高位往低位支点在pivot位那么这一位的贡献是digit × (pos - pivot)。左边为正右边为负或者反过来只要最后总和为0就行。这个力矩差的范围是多少假设最多19位每位最大9距离最大18那么单边最大力矩大约是9 × (12...18) 9 × 171 1539。两边差值范围大概在[-1539, 1539]之间。所以我们可以用一个偏移量offset 2000左右来把负数映射到数组下标。状态可以设计为dp[pos][pivot][sum]表示当前处理到第pos位支点在pivot当前力矩差为sum加上偏移量后的方案数。但这样三维数组pos最多19pivot最多19sum最多4000左右总状态数19 × 19 × 4000 ≈ 1.44M完全可接受。不过实际写的时候我们通常把pivot放在外层枚举dp数组只记pos和sum这样每次枚举pivot时清空dp数组。虽然多了一些重复计算但代码更清晰而且状态数更少。2.3 前导零的处理技巧前导零是数位DP里最容易出错的地方。对于平衡数这题前导零会影响支点的选择。比如数字00123实际上就是123但如果你把前导零也当成有效位支点位置就变了。处理方式有两种一种是在状态里加一个flag表示是否还在前导零阶段另一种是枚举支点时只考虑有效位。我比较推荐第一种因为更通用。具体来说在dfs过程中如果当前位之前全是前导零且当前位填0那么这一位不贡献力矩支点位置也不变或者说支点还没确定。只有当填了第一个非零数字后支点才真正开始起作用。但这样会带来一个问题支点是在枚举时固定的如果前导零导致实际有效位数变少支点位置可能需要调整。所以更稳妥的做法是在枚举支点时支点位置是相对于有效数字的位置。我们可以先确定数字的总位数然后枚举支点在这个位数中的位置。实际编码时我通常这样处理dfs(pos, pivot, sum, lead, limit)其中lead表示是否还在前导零。如果lead为真且当前填0那么sum不变继续下一位。如果lead为真且填了非零那么这一位开始贡献力矩距离是pos - pivot。2.4 记忆化的边界条件记忆化的条件是当没有limit限制时可以记录dp[pos][sum]的值。注意这里pivot是外层枚举的所以dp数组不需要包含pivot维度但每次换pivot要重新初始化。边界条件是pos 0时返回sum 0 ? 1 : 0。但要注意如果整个数都是前导零即数字0那么sum始终为0会被统计一次。由于我们枚举了所有支点0会被统计len次最后要减去(len - 1)。还有一个细节当lead为真时不应该记录dp值因为此时sum的状态依赖于前导零的处理不同支点下可能不同。不过由于pivot是外层枚举的lead为真时sum始终为0记录也无妨但为了安全起见通常不记录lead为真的状态。3. 完整代码实现与逐行解析3.1 代码框架与变量定义#include bits/stdc.h using namespace std; typedef long long ll; int digit[20]; ll dp[20][4000]; int pivot; ll dfs(int pos, int sum, bool lead, bool limit) { if (pos 0) return sum 0; if (!limit !lead dp[pos][sum] ! -1) return dp[pos][sum]; int up limit ? digit[pos] : 9; ll res 0; for (int i 0; i up; i) { if (lead i 0) { res dfs(pos - 1, sum, true, limit i up); } else { res dfs(pos - 1, sum i * (pos - pivot), false, limit i up); } } if (!limit !lead) dp[pos][sum] res; return res; } ll solve(ll n) { if (n 0) return 0; int len 0; while (n) { digit[len] n % 10; n / 10; } if (len 0) { digit[len] 0; } ll ans 0; for (pivot 0; pivot len; pivot) { memset(dp, -1, sizeof(dp)); ans dfs(len - 1, 2000, true, true); } return ans - (len - 1); } int main() { int T; cin T; while (T--) { ll L, R; cin L R; cout solve(R) - solve(L - 1) endl; } return 0; }这段代码就是完整的解法。下面我逐部分解释。3.2 dfs函数的参数含义与转移逻辑pos表示当前处理到第几位从高位往低位0是最高位len-1是最低位。注意这里的pos是从len-1递减到0所以pos - pivot就是当前位到支点的距离。如果pos pivot距离为正表示在支点左边如果pos pivot距离为负表示在支点右边。sum是当前力矩差初始值设为2000偏移量因为力矩差可能为负。最后判断sum 2000时表示平衡。lead表示是否还在前导零阶段。如果lead为真且当前填0那么这一位不贡献力矩继续下一位。如果填了非零lead变为false开始正常贡献。limit表示是否受到上界限制。如果limit为真当前位最多填digit[pos]否则可以填0到9。转移逻辑很直接枚举当前位填什么如果还在前导零且填0sum不变否则sum加上i × (pos - pivot)。然后递归下一位。3.3 solve函数的区间处理与支点枚举solve(n)计算的是[0, n]内平衡数的个数。如果n 0返回0。然后把n的每一位拆到digit数组里注意digit[0]是最低位digit[len-1]是最高位。但在dfs里pos是从len-1到0所以pos对应的是高位到低位。然后枚举pivot从0到len-1。每次枚举前清空dp数组。调用dfs(len-1, 2000, true, true)。最后把所有pivot的结果加起来减去(len - 1)。为什么减去(len - 1)因为数字0在每个pivot下都被统计了一次总共统计了len次但实际只应该算一次所以要减去len - 1次。3.4 偏移量的选择与数组大小偏移量选2000是经验值。最大力矩差是多少假设19位每位最大9距离最大18单边最大力矩是9 × (12...18) 9 × 171 1539。两边差值最大是1539 - 0 1539或者0 - 1539 -1539。所以sum的范围是[-1539, 1539]加上偏移量2000后范围是[461, 3539]。数组开4000足够。实际写的时候我习惯开dp[20][4000]偏移量用2000。这样既不会越界也不会浪费太多空间。3.5 时间复杂度的估算外层枚举pivot最多19次。每次dfs的状态数是pos × sum 19 × 4000 76000。每个状态转移最多10次。所以单次dfs大约是76000 × 10 760000次操作。总共19次pivot大约是1.44 × 10^7次操作。对于T组测试数据如果T 100总操作量是1.44 × 10^9可能会超时。优化方法不要每次pivot都清空dp数组而是把pivot也作为dp的一个维度。这样dp[pos][pivot][sum]状态数19 × 19 × 4000 1.44M但只需要计算一次。不过内存会大一些1.44M × 8字节 ≈ 11.5MB可以接受。或者注意到solve(R)和solve(L-1)会重复计算很多状态可以把dp数组做成全局的只初始化一次。但pivot不同时状态不能共用所以还是需要pivot维度。我实际测试下来对于T 100R 10^18的情况不优化也能过因为很多状态实际上不会被访问到。但如果T更大建议加上pivot维度。4. 常见错误与调试经验4.1 前导零导致的重复计数最常见的错误就是前导零处理不当。比如数字0如果不在最后减去(len - 1)会被统计len次。还有数字10如果前导零处理不对可能会把01当成一个有效的两位数支点位置就错了。我当初写的时候犯过一个错误在lead为真时仍然让sum加上i × (pos - pivot)。这样当i 0时sum不变看起来没问题。但当i 0时lead变为false这一位的贡献是对的。问题在于如果整个数都是前导零sum始终为0最后返回1这是对的。但如果前导零后面有非零数字支点位置是相对于整个len的而不是相对于有效数字的。比如数字00123len 5支点枚举的是0到4但实际有效数字是123支点应该在1到3之间。这样就会导致错误。解决方法在枚举pivot时只考虑有效位。但有效位在dfs之前不知道所以更通用的做法是在dfs里动态调整。不过这样比较复杂。我推荐的做法是先确定数字的实际长度然后在solve里枚举pivot时只枚举0到len-1但在dfs里如果lead为真支点位置实际上还没确定所以距离计算要特殊处理。实际编码时我采用的方式是在dfs里如果lead为真且i 0直接递归下一位不贡献力矩。这样支点位置pivot是相对于整个len的但前导零不贡献力矩所以实际效果等价于支点相对于有效数字。但要注意如果整个数都是0那么所有pivot下sum都是0最后减去(len - 1)即可。4.2 力矩差值为负的处理sum可能为负所以要用偏移量。我见过有人用map来存状态虽然可以但效率低。用数组加偏移量是最快的。偏移量选多少我一般选2000因为最大力矩差不超过1600。但如果你不确定可以选3000或4000数组开大一点不会影响正确性只是多占点内存。4.3 多组测试数据的初始化问题如果有多组测试数据dp数组每次都要清空。但清空整个4000 × 20的数组需要时间。优化方法是把dp数组初始化为-1但只初始化用到的部分。或者用时间戳标记避免重复清空。我通常的做法是在solve函数里每次枚举pivot时memset(dp, -1, sizeof(dp))。虽然有点慢但对于T 100来说100 × 19 × 4000 × 8字节 ≈ 60MB的写入现代计算机几毫秒就完成了可以接受。如果T很大比如10^5那就需要优化。可以把dp数组做成全局的用pivot作为一维这样只需要初始化一次。但要注意solve(R)和solve(L-1)会共用dp数组所以dp数组不能包含limit和lead的信息这些在记忆化时已经排除了。4.4 边界情况L 0, R 0如果L 0, R 0答案应该是10是平衡数。solve(0)会返回1solve(-1)返回0所以结果是1。但要注意solve(0)里len 1pivot枚举0到0dfs返回1最后减去(len - 1) 0所以结果是1。正确。如果L 1, R 1答案应该是11是平衡数支点在1本身两边力矩都是0。solve(1)返回20和1solve(0)返回1所以结果是1。正确。4.5 常见问题速查表问题现象可能原因解决方法答案偏大前导零重复计数最后减去(len - 1)答案偏小支点枚举范围不对确保pivot从0到len-1运行超时dp数组未记忆化检查!limit !lead条件数组越界偏移量太小增大偏移量到2000以上多组数据答案错误dp数组未清空每次solve前memset0被统计多次0的特殊性最后减去(len - 1)5. 数位DP的通用套路与扩展5.1 数位DP的通用模板数位DP的题目千变万化但核心套路是固定的。我总结了一个通用模板ll dfs(int pos, /* 状态参数 */, bool lead, bool limit) { if (pos 0) return /* 边界条件 */; if (!limit !lead dp[pos][/* 状态 */] ! -1) return dp[pos][/* 状态 */]; int up limit ? digit[pos] : 9; ll res 0; for (int i 0; i up; i) { if (lead i 0) { res dfs(pos - 1, /* 状态不变 */, true, limit i up); } else { res dfs(pos - 1, /* 状态转移 */, false, limit i up); } } if (!limit !lead) dp[pos][/* 状态 */] res; return res; }这个模板适用于绝大多数数位DP题目。区别只在于状态参数的设计和转移方程。5.2 从平衡数到其他数位DP题平衡数这题的状态是力矩差其他题可能是数位和、数位乘积、模数等。比如统计数位和能被某个数整除的数的个数状态就是数位和对模数的余数。统计包含某些数字的数的个数状态就是是否出现过这些数字的标记。我建议初学者从平衡数这题入手因为它状态简单但又包含了数位DP的所有关键点支点枚举、前导零、记忆化、区间减法。把这题写熟练了其他题就是换汤不换药。5.3 记忆化搜索与递推的取舍数位DP有两种写法记忆化搜索和递推。记忆化搜索更直观代码更短适合初学者。递推效率更高但代码复杂容易出错。我个人的习惯是先用记忆化搜索写一遍确保正确。如果超时再考虑改成递推或者优化状态。对于平衡数这题记忆化搜索完全够用不需要递推。5.4 实操心得与避坑建议第一前导零一定要处理。我见过太多人因为前导零导致答案错误调试半天找不到原因。记住前导零不贡献力矩但支点位置是相对于整个数字的。第二偏移量要足够大。不要为了省内存把偏移量设得很小否则会越界。我一般设2000数组开4000稳妥。第三多组数据要清空dp数组。如果不清空上一组的数据会污染下一组的结果。虽然memset有点慢但正确性优先。第四0要特殊处理。0是平衡数但在每个支点下都被统计了一次最后要减去(len - 1)。这个细节很容易忽略。第五支点枚举范围是0到len-1。不要从1开始也不要到len结束。支点可以在最高位也可以在最低位。第六limit和lead为真时不记录dp值。因为这两种状态下后续的决策依赖于前面的限制不是独立的状态。第七用long long存答案。虽然平衡数的个数不会超过R但R可能到10^18int会溢出。第八输入输出用scanf/printf或者关闭同步的cin/cout。如果T很大cin/cout可能会慢。5.5 性能优化技巧如果T很大比如10^5那么每次solve都要重新计算效率很低。优化方法是把dp数组做成全局的用pivot作为一维这样只需要初始化一次。但要注意solve(R)和solve(L-1)会共用dp数组所以dp数组不能包含limit和lead的信息。具体做法dp[pos][pivot][sum]初始化为-1。在dfs里如果!limit !lead就记录dp[pos][pivot][sum]。这样无论solve多少次dp数组只需要初始化一次。但内存会大一些19 × 19 × 4000 × 8字节 ≈ 11.5MB可以接受。另外可以把digit数组和len做成全局的避免每次solve都重新计算。但要注意solve(R)和solve(L-1)的digit数组不同所以每次solve前要重新拆分。还有一个优化如果R 0直接返回1。如果L 0solve(L-1)返回0。这些边界情况可以提前判断避免不必要的计算。6. 从解题到实战数位DP的应用场景6.1 数位DP在竞赛中的常见题型数位DP在算法竞赛中出现频率很高常见的题型包括统计区间内满足数位和条件的数、统计区间内包含某些数字的数、统计区间内数位乘积满足条件的数、统计区间内数位排列满足条件的数等。平衡数这题属于“数位加权和”类型特点是每一位的贡献与位置有关。类似的题目还有统计区间内数位平方和满足条件的数、统计区间内数位立方和满足条件的数等。6.2 数位DP在实际工程中的应用虽然数位DP看起来像是竞赛专用但它在实际工程中也有应用。比如生成满足某些数位条件的ID、校验码的生成与验证、密码强度的统计等。我做过一个项目需要生成一批满足特定数位模式的序列号。用数位DP可以快速统计出满足条件的序列号有多少个然后按需生成。比暴力枚举快了几个数量级。6.3 学习数位DP的路线建议如果你刚接触数位DP我建议按这个顺序刷题先做最简单的“统计区间内不含某些数字的数”再做“统计区间内数位和能被整除的数”然后做平衡数这题最后做带模数或者多状态的数位DP。每道题都要自己先想状态设计想不出来再看题解。看完题解后一定要自己手写一遍不要复制粘贴。写完后自己造几组测试数据验证正确性。6.4 个人体会数位DP这玩意儿说难不难说简单也不简单。关键是要理解“逐位决策”和“记忆化”这两个核心思想。一旦理解了大部分题都能套模板。我当初学的时候卡在前导零处理上很久。后来想明白了前导零就是“还没开始填有效数字”的状态在这个状态下任何位都不贡献支点也没确定。把这个状态单独处理问题就迎刃而解了。还有一点不要怕写错。数位DP的代码虽然不长但细节很多。多写几遍多调试几次自然就熟练了。我现在的习惯是每道数位DP题都先写记忆化搜索确保正确后再考虑优化。这样虽然代码长一点但不容易出错。最后分享一个小技巧如果实在想不出状态怎么设计就先写暴力然后观察暴力过程中哪些状态是重复的把这些状态提取出来就是DP的状态。这个方法虽然笨但很有效。