数位DP实战：平衡数问题详解与记忆化搜索模板

1. 从一道题看数位DP的本质1.1 这道题到底在问什么先把这个题目的意思说清楚。所谓平衡数指的是这样一个数字存在某一个数位作为支点使得支点左边所有数字对支点的力矩之和等于支点右边所有数字对支点的力矩之和。力矩的计算方式是数字本身乘以它到支点的距离。举个具体的例子数字4139。如果以3这个位置作为支点3左边是4和1右边是9。左边力矩4距离支点2位贡献4×281距离支点1位贡献1×11左边合计9。右边力矩9距离支点1位贡献9×19。左右相等所以4139是一个平衡数。题目要求的是给定一个区间[a, b]统计这个区间内有多少个平衡数。a和b的范围可以到10的18次方也就是long long级别。暴力枚举显然不可能一个区间动辄上亿个数字必须用数位DP来做。我第一次接触这个题的时候第一反应是枚举支点位置然后对每个支点做一次数位DP。这个思路是对的但里面有几个坑后面会详细说。1.2 为什么暴力不行数位DP为什么合适先算一笔账。假设区间是[1, 10^18]暴力枚举需要遍历10^18个数字即使每个数字只花1纳秒判断也要10^9秒也就是三十多年。这显然不现实。数位DP的核心思想是把数字按位拆开逐位确定同时记录当前状态。对于平衡数问题状态需要记录什么呢我们需要知道当前处理到第几位、支点在哪一位、当前左边力矩减去右边力矩的差值是多少。这样在枚举每一位的数字时就能更新这个差值最后判断差值是否为零。数位DP的时间复杂度大约是状态数乘以每位可能的取值数。状态数大概是位数×支点位置×力矩差值范围。位数最多19位10^18是19位支点位置最多19种力矩差值范围大概在-1500到1500之间每位最大9距离最大18总和约9×18×19/2≈1539。所以状态数大约19×19×3000≈108万再乘以每位10种取值大约一千万次操作完全可以在1秒内跑完。这就是数位DP的威力把10^18的枚举量压缩到了10^6级别。1.3 数位DP的两种写法递推与记忆化搜索数位DP通常有两种实现方式。一种是递推预处理出dp数组然后按位统计。另一种是记忆化搜索写一个递归函数带上限标记用记忆化数组存结果。对于这个题我推荐用记忆化搜索。原因有几个第一记忆化搜索的代码结构更清晰不容易出错第二这个题的状态转移不是简单的按位递推因为力矩差值的更新依赖于当前位和支点的相对位置递推写起来比较绕第三记忆化搜索更容易处理前导零的问题。当然递推也有它的优势比如常数更小但在这个题的数据范围下两者的差距可以忽略不计。所以下面我主要讲记忆化搜索的写法递推的思路也会提一下方便你对比理解。2. 核心思路拆解与状态设计2.1 枚举支点为什么必须固定支点平衡数的定义里支点可以是任意一个数位。一个数字可能有多个支点吗理论上可能但实际上一旦确定了支点力矩平衡的条件就唯一确定了。如果我们不固定支点就没法定义“左边”和“右边”也就没法计算力矩差。所以自然的思路是枚举支点的位置对每个支点位置分别做一次数位DP统计以该位置为支点的平衡数个数最后把所有支点的结果加起来。但这里有一个重复计数的问题。如果一个数字有多个支点它会被统计多次。比如0这个数字它的每一位都可以作为支点因为左右力矩都是0。实际上除了0以外一个数字最多只有一个支点。这个结论可以简单证明假设有两个不同的支点那么两个支点之间的力矩关系会矛盾。所以重复计数只发生在0这个数字上。处理方法是在枚举支点时从最低位开始枚举或者最后减去重复计数的部分。更常见的做法是在DP过程中允许前导零最后把0的重复计数减掉。具体来说如果枚举了len个支点位置那么0被统计了len次需要减去(len-1)次。我个人的习惯是在solve函数里枚举支点从0到len-10表示最低位每次调用dfs然后把结果累加最后减去(len-1)。这样写比较直观。2.2 状态定义pos、pivot、sum记忆化搜索的状态通常用几个参数来描述。对于这个题我们需要pos当前处理到第几位。从高位向低位处理pos表示当前正在决定的位。pivot支点的位置。这个在整个DP过程中是固定的因为我们是枚举支点后分别做DP。sum当前左边力矩减去右边力矩的差值。注意这个差值是在处理过程中动态更新的。limit上限标记表示当前位是否受到原数字上界的限制。lead前导零标记表示当前是否还在处理前导零。其中limit和lead是记忆化搜索的常规参数不需要存入dp数组。dp数组只需要记录pos、pivot、sum这三个维度的结果。sum的范围需要估算一下。最坏情况下所有位都是9支点在最高位那么右边力矩最大是9×(12...18)9×1711539。所以sum的范围可以取[-1539, 1539]加上偏移量变成[0, 3078]。实际写代码时可以用一个偏移量OFFSET2000数组开4000左右就够了。2.3 状态转移逐位枚举与力矩更新状态转移的过程是这样的从高位到低位对于当前位pos枚举这一位可以取的数字d0到9如果limit为真则最多到当前位的上界。然后计算这一位对力矩差的贡献。贡献的计算依赖于pos和pivot的关系。如果pos pivot说明当前位在支点左边因为高位在左贡献是d × (pos - pivot)。如果pos pivot说明当前位在支点右边贡献是-d × (pivot - pos)。如果pos pivot贡献是0因为支点上的数字不产生力矩。更新后的sum sum 贡献。然后递归到pos-1位。当pos 0时如果sum 0且没有前导零或者允许前导零但最后判断就返回1否则返回0。这里有一个细节前导零的处理。如果当前还在前导零状态那么这一位取0时不应该产生力矩贡献因为前导零不算数字的一部分。所以当lead为真且d为0时贡献为0并且lead继续保持为真。只有当d不为0时lead才变为假开始正常计算力矩。这个细节很容易出错。我见过不少人在处理前导零时忘记把lead传递下去导致0被重复计数或者前导零被错误地计算了力矩。3. 代码实现与关键细节3.1 记忆化搜索的完整框架下面给出记忆化搜索的完整代码框架。我用C来写因为这是算法竞赛中最常用的语言。#include bits/stdc.h using namespace std; typedef long long ll; ll dp[20][20][4000]; int digit[20]; int len; ll dfs(int pos, int pivot, int sum, bool limit, bool lead) { if (pos 0) { return sum 0 ? 1 : 0; } if (!limit !lead dp[pos][pivot][sum 2000] ! -1) { return dp[pos][pivot][sum 2000]; } int up limit ? digit[pos] : 9; ll res 0; for (int d 0; d up; d) { if (lead d 0) { res dfs(pos - 1, pivot, sum, limit d up, true); } else { int contrib 0; if (pos pivot) { contrib d * (pos - pivot); } else if (pos pivot) { contrib -d * (pivot - pos); } res dfs(pos - 1, pivot, sum contrib, limit d up, false); } } if (!limit !lead) { dp[pos][pivot][sum 2000] res; } return res; } ll solve(ll x) { if (x 0) return 0; len 0; while (x) { digit[len] x % 10; x / 10; } if (len 0) { digit[len] 0; } ll ans 0; for (int pivot 0; pivot len; pivot) { ans dfs(len - 1, pivot, 0, true, true); } ans - (len - 1); return ans; } int main() { memset(dp, -1, sizeof(dp)); int T; cin T; while (T--) { ll a, b; cin a b; cout solve(b) - solve(a - 1) endl; } return 0; }这段代码有几个关键点需要解释。第一dp数组的初始化。因为dp数组只依赖于pos、pivot、sum与limit和lead无关所以可以在主函数开头一次性初始化为-1。每次查询时如果遇到!limit !lead的情况就可以直接查表。第二digit数组的存储。我们把数字x的每一位从低位到高位存入digit数组digit[0]是最低位digit[len-1]是最高位。在dfs中pos从len-1开始递减到0所以pos越大表示越高位。第三支点的枚举。pivot从0到len-1对应从最低位到最高位。每次调用dfs时初始sum为0limit为truelead为true。第四重复计数的处理。ans减去(len-1)是因为0被统计了len次需要减去多余的len-1次。注意如果x0len1那么减去0结果正确。3.2 力矩贡献的计算正负号与距离力矩贡献的计算是这道题的核心。我再详细说一下。假设当前处理到第pos位支点在pivot位。因为pos是从高位向低位递减的所以pos pivot表示当前位在支点的左边高位侧pos pivot表示当前位在支点的右边低位侧。对于左边的位它产生的力矩是d × (pos - pivot)这个力矩是正的我们约定左边为正。对于右边的位它产生的力矩是d × (pivot - pos)但我们希望左右力矩相等所以右边应该贡献负值即-d × (pivot - pos)。这样sum就是左边力矩减去右边力矩。最后sum 0就表示平衡。这里有一个容易混淆的地方pos和pivot的大小关系。因为pos是从高位向低位递减的所以pos pivot确实表示高位侧。但如果你用递推的写法从低位向高位处理那么大小关系就反过来了。所以写代码时一定要想清楚你的处理方向。我个人的习惯是从高位向低位处理因为这样更符合数位DP的常规写法也更容易处理limit标记。3.3 前导零的处理为什么不能简单忽略前导零的处理是数位DP中的一个经典难点。在这个题里前导零的影响体现在两个方面。第一前导零不应该产生力矩。比如数字00123实际上就是123前导的两个0不应该被计算。如果我们在lead为真时仍然计算0的力矩那么0 × 距离 0看起来没有影响。但问题是前导零会改变支点的位置。比如00123如果支点在第一个0的位置那么实际上这个支点是不存在的因为前导零不算数字的一部分。第二前导零会影响数字的长度。比如0它的长度是1但如果我们允许前导零它可能被表示成00、000等。这会导致0被多次统计。所以正确的做法是当lead为真且当前位取0时不计算力矩并且lead继续保持为真。只有当取非零数字时lead才变为假开始正常计算。这样0这个数字在DP过程中只会被统计一次当所有位都是0时但因为我们枚举了len个支点所以0被统计了len次。这就是为什么最后要减去(len-1)。3.4 记忆化数组的维度与偏移量dp数组的维度是[20][20][4000]。第一个维度是pos最多19位开20够用。第二个维度是pivot最多19个支点开20够用。第三个维度是sum范围是[-1539, 1539]加上偏移量2000后是[461, 3539]开4000够用。偏移量的选择需要保证sum OFFSET不会越界。最坏情况下sum最小是-1539加上2000是461大于0sum最大是1539加上2000是3539小于4000。所以OFFSET2000数组大小4000是安全的。如果你不确定范围可以开大一点比如5000代价是内存稍微多一点但在这个题里完全可以接受。4. 常见问题与排查技巧4.1 为什么我的答案总是多1或少1这是数位DP中最常见的问题通常出在边界处理上。具体到这个题有几个地方容易出错。第一solve(0)的返回值。如果a0那么solve(a-1)就是solve(-1)。我在代码里加了if (x 0) return 0;来处理这种情况。如果你忘了这个判断solve(-1)可能会返回错误的结果。第二0的重复计数。前面说过0被统计了len次需要减去(len-1)。如果你忘了减答案会多出(len-1)。如果你减错了比如减了len答案会少1。第三len的计算。如果x0while循环不会执行len保持为0。我在代码里加了if (len 0) digit[len] 0;来处理这种情况。如果你忘了这个len0会导致支点枚举循环不执行ans0但实际答案应该是10是平衡数。第四区间减法的边界。solve(b) - solve(a-1)是标准写法但如果a0a-1-1solve(-1)必须返回0。这个已经在第一点里说了。我建议你在写完代码后先用小数据测试。比如a0, b100手动算一下答案然后和程序输出对比。如果对不上就逐步缩小范围找到出错的数字。4.2 记忆化搜索超时怎么办记忆化搜索的超时通常有两个原因状态数太多或者记忆化没有生效。状态数太多的情况如果你把limit和lead也放进了dp数组那么状态数会爆炸。因为limit和lead的组合很多而且每次查询都要重新计算。正确的做法是只把pos、pivot、sum存入dp数组limit和lead作为递归参数传递。记忆化没有生效的情况如果你在limit为真时也查表那么结果可能不正确因为limit为真时的结果依赖于具体的上界。所以查表条件必须是!limit !lead。如果你写成了!limit那么lead为真时也会查表但lead为真时的结果和lead为假时不同会导致错误。另外dp数组的初始化也很重要。如果你在每次查询前都memset那么记忆化的效果就没了。正确的做法是在主函数开头一次性初始化然后所有查询共享。4.3 支点枚举的顺序有影响吗支点枚举的顺序没有影响因为每个支点的DP是独立的。但如果你在枚举支点时把pivot作为dp数组的一个维度那么不同支点的结果会分别存储互不干扰。我见过有人把pivot作为全局变量然后在dfs中直接使用这样会导致dp数组无法正确记忆化因为不同支点的结果会混在一起。正确的做法是把pivot作为dfs的参数并且作为dp数组的一个维度。4.4 力矩差值的范围怎么确定力矩差值的范围取决于数字的位数和每位的大小。最坏情况下所有位都是9支点在最高位那么右边力矩最大是9×(12...18)9×1711539。所以sum的范围是[-1539, 1539]。但实际写代码时你可以开大一点比如[-2000, 2000]这样更安全。偏移量取2000数组大小4000足够了。如果你不确定可以写一个程序枚举所有可能的sum值找到最大值和最小值。但在这个题里上面的估算已经足够了。4.5 常见问题速查表问题现象可能原因解决方法答案多10被重复计数减去(len-1)答案少1solve(-1)返回错误加if (x 0) return 0答案多len-1忘了减重复计数减去(len-1)答案少len-1减多了检查减的是len-1还是len超时记忆化没生效检查查表条件是否为!limit !lead超时dp数组每次查询都memset改为一次性初始化答案错误前导零处理不当检查lead为真时是否计算了力矩答案错误力矩正负号搞反检查pos和pivot的大小关系答案错误支点枚举范围不对检查pivot是否从0到len-1答案错误len计算错误检查x0时len是否为15. 从这道题延伸出的数位DP通用套路5.1 数位DP的适用场景数位DP适用于那些需要统计满足某种条件的数字个数的问题条件通常与数字的每一位有关。比如统计区间内不含某个数字的数字个数、统计区间内各位数字之和为某个值的数字个数、统计区间内满足某种数位关系的数字个数。这个题的条件是力矩平衡属于数位关系的一种。类似的还有统计区间内相邻两位之差不超过某个值的数字个数、统计区间内各位数字乘积为某个值的数字个数等。数位DP的核心是把数字按位拆开逐位确定同时记录当前状态。状态的设计是关键需要根据具体条件来确定。5.2 记忆化搜索的通用模板记忆化搜索的数位DP有一个通用模板你可以直接套用ll dfs(int pos, /* 其他状态参数 */, bool limit, bool lead) { if (pos 0) { return /* 判断是否满足条件 */; } if (!limit !lead dp[pos][/* 其他状态 */] ! -1) { return dp[pos][/* 其他状态 */]; } int up limit ? digit[pos] : 9; ll res 0; for (int d 0; d up; d) { if (lead d 0) { res dfs(pos - 1, /* 状态不变 */, limit d up, true); } else { res dfs(pos - 1, /* 更新状态 */, limit d up, false); } } if (!limit !lead) { dp[pos][/* 其他状态 */] res; } return res; }这个模板的关键点第一pos 0时判断条件第二查表条件!limit !lead第三前导零的处理第四状态更新。你可以把这个模板记下来遇到数位DP的题直接套用只需要根据具体条件修改状态参数和状态更新逻辑。5.3 递推写法的对比递推写法的数位DP通常需要预处理dp数组然后按位统计。对于这个题递推的写法大概是先预处理出dp[pos][pivot][sum]表示从第pos位到最低位支点在pivot当前力矩差为sum的方案数。然后对于每个查询从高位到低位逐位统计。递推的优点是常数小缺点是代码复杂容易出错。特别是这个题的状态转移依赖于pos和pivot的关系递推写起来比较绕。我个人的建议是如果时间充裕用记忆化搜索代码清晰不容易出错如果时间紧张或者需要卡常数可以考虑递推但一定要仔细检查状态转移。5.4 数位DP的调试技巧数位DP的调试比较麻烦因为状态多边界多。我通常用以下几个技巧。第一写一个暴力程序枚举小区间内的所有数字判断是否满足条件然后和数位DP的结果对比。如果对不上就逐步缩小范围找到出错的数字。第二在dfs中加打印语句输出每次递归的pos、pivot、sum、limit、lead和返回值。这样可以追踪DP的过程找到错误的地方。第三检查边界条件。比如pos 0时的返回值、limit为真时的上界、lead为真时的处理、dp数组的初始化等。第四检查状态范围。比如sum的范围是否足够、dp数组的大小是否够用、偏移量是否合适等。第五检查重复计数。比如0是否被重复统计、支点枚举是否覆盖了所有情况等。6. 实操中的经验与避坑指南6.1 我踩过的坑前导零导致0被重复计数我第一次写这个题的时候前导零处理得不对。我在lead为真时也计算了力矩虽然0的力矩是0但支点的位置被改变了。结果0被统计了多次答案偏大。后来我改成lead为真且d0时不计算力矩lead继续保持为真。这样0只在所有位都是0时被统计一次。但因为我枚举了len个支点所以0被统计了len次最后减去(len-1)才正确。这个坑很隐蔽因为0的力矩是0看起来没有影响。但实际上前导零改变了支点的位置导致0被重复统计。所以前导零的处理一定要小心。6.2 我踩过的坑dp数组忘记初始化有一次我写代码忘了在main函数开头memset(dp, -1, sizeof(dp))结果dp数组的初始值是随机的导致答案错误。这个错误很隐蔽因为有时候随机值恰好是-1程序能跑对但换个环境就错了。所以我的习惯是写完代码后先检查dp数组的初始化。如果是多组测试数据确保dp数组只初始化一次而不是每次查询都初始化。6.3 我踩过的坑支点枚举范围错误有一次我把支点枚举范围写成了从1到len结果漏掉了支点在最低位的情况。因为pivot是从0开始编号的0表示最低位所以枚举范围应该是0到len-1。这个错误会导致答案偏小因为支点在最低位的平衡数没有被统计。比如数字1支点在最低位也是最高位左右力矩都是0是平衡数。如果漏掉了pivot01就不会被统计。所以支点枚举范围一定要仔细检查。6.4 实操心得先用小数据验证我写数位DP的习惯是先用小数据验证。比如a0, b100手动算一下答案然后和程序输出对比。如果对不上就逐步缩小范围找到出错的数字。手动算的时候可以写一个暴力程序枚举所有数字判断是否满足条件。然后和数位DP的结果对比。如果暴力程序的结果和数位DP的结果一致说明数位DP是对的如果不一致就找到第一个不一致的数字分析原因。这个习惯帮我省了很多时间因为数位DP的边界问题很多小数据验证可以快速定位错误。6.5 实操心得注意数据范围这个题的a和b可以到10的18次方所以必须用long long。如果你用了int会溢出导致答案错误。另外solve函数的参数也必须是long long。如果你传了int会在参数传递时溢出。还有digit数组的大小要足够。10的18次方是19位所以digit数组开20就够了。但如果你不确定可以开大一点比如30。6.6 实操心得多组测试数据的处理这个题有多组测试数据所以dp数组的初始化必须在所有查询之前完成而不是每次查询都初始化。如果你每次查询都memset那么记忆化的效果就没了会超时。正确的做法是在main函数开头memset一次然后所有查询共享dp数组。因为dp数组只依赖于pos、pivot、sum与具体的查询无关所以可以共享。这个技巧在数位DP中很常用可以大大提高效率。6.7 实操心得偏移量的选择偏移量的选择需要保证sum OFFSET不会越界。我通常取OFFSET2000数组大小4000。这个范围对于这个题足够了。如果你不确定范围可以开大一点比如OFFSET3000数组大小6000。代价是内存稍微多一点但在这个题里完全可以接受。另外偏移量必须是常数不能是变量。因为dp数组的大小需要在编译时确定。6.8 实操心得递归深度这个题的递归深度最多19层不会栈溢出。但如果你的位数更多比如100位那么递归深度可能达到100层这时候需要考虑栈溢出的问题。对于这个题19层完全没问题。但如果你遇到位数更多的题可以考虑用递推或者增加栈的大小。7. 完整代码与测试用例7.1 完整代码前面已经给出了完整代码这里再补充一些注释和测试用例。#include bits/stdc.h using namespace std; typedef long long ll; // dp[pos][pivot][sum OFFSET] // pos: 当前处理到第几位从高位向低位范围[0, 19] // pivot: 支点位置范围[0, 19] // sum: 左边力矩减去右边力矩范围[-1539, 1539] // OFFSET: 偏移量取2000 ll dp[20][20][4000]; int digit[20]; int len; ll dfs(int pos, int pivot, int sum, bool limit, bool lead) { if (pos 0) { // 所有位处理完毕sum为0表示平衡 return sum 0 ? 1 : 0; } // 记忆化查表注意!limit !lead if (!limit !lead dp[pos][pivot][sum 2000] ! -1) { return dp[pos][pivot][sum 2000]; } int up limit ? digit[pos] : 9; ll res 0; for (int d 0; d up; d) { if (lead d 0) { // 前导零不计算力矩lead继续保持 res dfs(pos - 1, pivot, sum, limit d up, true); } else { // 计算力矩贡献 int contrib 0; if (pos pivot) { contrib d * (pos - pivot); } else if (pos pivot) { contrib -d * (pivot - pos); } res dfs(pos - 1, pivot, sum contrib, limit d up, false); } } // 记忆化存表 if (!limit !lead) { dp[pos][pivot][sum 2000] res; } return res; } ll solve(ll x) { if (x 0) return 0; len 0; while (x) { digit[len] x % 10; x / 10; } if (len 0) { digit[len] 0; } ll ans 0; for (int pivot 0; pivot len; pivot) { ans dfs(len - 1, pivot, 0, true, true); } // 减去0的重复计数 ans - (len - 1); return ans; } int main() { memset(dp, -1, sizeof(dp)); int T; cin T; while (T--) { ll a, b; cin a b; cout solve(b) - solve(a - 1) endl; } return 0; }7.2 测试用例输入输出说明1 111是平衡数1 10100-9都是平衡数共10个1 100190-9共10个11-99中平衡数有9个11,22,...,99共19个1 1000280-9共10个11-99共9个100-999中平衡数有9个111,222,...,999共28个1 1000037类似规律每增加一位平衡数增加9个注意上面的测试用例是我根据规律推算的实际运行时可能会有细微差别。你可以用暴力程序验证。7.3 暴力验证程序#include bits/stdc.h using namespace std; typedef long long ll; bool isBalanced(ll x) { if (x 0) return false; if (x 0) return true; vectorint digits; while (x) { digits.push_back(x % 10); x / 10; } reverse(digits.begin(), digits.end()); int n digits.size(); for (int pivot 0; pivot n; pivot) { ll left 0, right 0; for (int i 0; i pivot; i) { left digits[i] * (pivot - i); } for (int i pivot 1; i n; i) { right digits[i] * (i - pivot); } if (left right) return true; } return false; } int main() { for (ll i 0; i 10000; i) { if (isBalanced(i)) { cout i ; } } cout endl; return 0; }这个暴力程序可以枚举0到10000的所有平衡数你可以用它来验证数位DP的结果。8. 数位DP的进阶思考8.1 如果支点不固定怎么办这个题的支点是固定的我们枚举了所有可能的支点。但如果题目要求的是“存在至少一个支点”那么我们的做法是正确的。如果题目要求的是“支点必须是最高位”或者“支点必须是最低位”那么就不需要枚举支点直接做一次DP即可。所以支点是否固定决定了是否需要枚举支点。这个题是“存在至少一个支点”所以需要枚举。8.2 如果力矩的定义不同怎么办这个题的力矩是数字乘以距离。如果力矩的定义不同比如数字乘以距离的平方那么状态转移就需要修改。但核心思路是一样的记录当前力矩差最后判断是否为零。所以数位DP的核心是状态设计只要状态设计对了转移逻辑就是自然的。8.3 如果数字的范围更大怎么办如果数字的范围更大比如10的100次方那么位数就是100位状态数会增加到100×100×30000≈3亿可能超时。这时候需要考虑优化比如用递推前缀和或者用矩阵快速幂。但对于这个题10的18次方已经足够了不需要考虑更大的范围。8.4 数位DP的变种数位DP有很多变种比如统计满足条件的数字个数、统计满足条件的数字之和、统计满足条件的数字的平方和等。这个题是统计个数所以dp数组存的是方案数。如果是统计和dp数组需要存两个值方案数和总和。这些变种的核心思路是一样的只是状态和转移略有不同。掌握了这个题其他变种也就容易了。8.5 数位DP的优化技巧数位DP的优化主要有两个方向减少状态数和减少转移数。减少状态数比如把pivot作为全局变量而不是dp数组的维度这样可以减少一维。但这样会导致不同支点的结果无法共享需要每次重新计算。对于这个题因为支点枚举次数不多最多19次所以影响不大。减少转移数比如预处理出每个状态的转移避免重复计算。但对于这个题转移很简单不需要优化。另外记忆化搜索的常数比递推大如果时间紧张可以考虑递推。但在这个题里记忆化搜索已经足够快了。8.6 数位DP的常见错误总结最后总结一下数位DP的常见错误供你参考。第一前导零处理不当。这是最常见的错误表现为0被重复计数或者前导零被错误地计算了力矩。第二记忆化查表条件错误。必须是!limit !lead缺一不可。第三dp数组初始化错误。必须一次性初始化不能每次查询都初始化。第四边界条件错误。比如pos 0时的返回值、solve(-1)的处理、len的计算等。第五状态范围错误。比如sum的范围不够、dp数组大小不够、偏移量不合适等。第六支点枚举范围错误。必须是0到len-1不能多也不能少。第七重复计数处理错误。0被统计了len次需要减去(len-1)。第八数据范围错误。必须用long long不能用int。这些错误我都踩过希望你能避开。数位DP的调试比较麻烦但只要细心一定能写对。8.7 个人体会数位DP这个知识点刚开始学的时候觉得很难状态设计、边界处理、前导零每一个都是坑。但写多了之后发现其实套路很固定枚举状态、记忆化搜索、处理边界。只要掌握了模板大部分数位DP的题都能套用。这个平衡数的题是一个很好的数位DP练习题。它包含了数位DP的核心要素状态设计、力矩计算、前导零处理、重复计数处理。把这个题吃透数位DP就算入门了。我建议你把这个题的代码自己敲一遍不要复制粘贴。敲的过程中你会遇到各种问题解决这些问题你就真正掌握了数位DP。最后再分享一个小技巧如果你不确定自己的数位DP写得对不对可以写一个暴力程序枚举小区间内的所有数字和数位DP的结果对比。这个方法虽然笨但非常有效可以帮你快速定位错误。这个题后续还可以这样扩展把力矩的定义改成数字乘以距离的平方或者把支点的条件改成左右力矩之差不超过某个值。这些扩展可以帮你更深入地理解数位DP的状态设计和转移逻辑。