1. 项目概述当“计数”遇上“数位”在算法竞赛和面试中我们常常会遇到一类让人头疼的问题给定一个范围[a, b]要求统计在这个范围内所有数字的每一位上某个特定数字比如数字0到9出现的总次数。例如问在1到100之间数字1出现了多少次手动数一数或许还行但如果范围是[1, 10^9]呢这类问题就是典型的“计数问题”。暴力枚举是行不通的时间复杂度是O(n * log10(n))对于大数据范围瞬间超时。这时就需要一种更聪明的方法——数位统计动态规划。它本质上是动态规划思想在数位统计场景下的精妙应用通过“分类讨论”和“状态记忆”将看似庞大的计数问题分解为对数字每一位的独立处理从而在O(log10(n))的时间复杂度内得到答案。对于C开发者尤其是参与算法竞赛或准备面试的同学掌握数位统计DP是突破瓶颈、解决复杂计数问题的关键技能。今天我们就来彻底拆解这个“计数问题”从核心思想到代码实现一步步构建起你的数位DP武器库。2. 核心思路拆解化整为零与状态定义数位统计DP的核心在于“按位处理”和“状态压缩”。我们不会去遍历每一个数字而是去考虑构成这些数字的每一位。想象一下我们要统计1到abcde这个五位数之间数字k出现的次数。我们可以分别统计数字k在万位、千位、百位、十位、个位上出现的次数然后加起来。2.1 关键思想分情况讨论对于某一个特定的数位比如百位数字k在这个位置上出现的次数取决于这个位置前面和后面的数字。以一个具体的例子说明统计1到abcdefg之间数字1在第四位千位上出现的次数。情况一千位数字小于1。如果原数字的千位是0那么要想千位是1前面三位abc可以从000到abc-1任意取后面三位defg可以从0000到9999任意取。贡献为(abc) * 10^3。情况二千位数字等于1。这又分为两种子情况如果原数字千位就是1那么前面三位固定为abc后面三位只能从000取到defg不能超过原数。贡献为defg 1。如果原数字千位大于1那么当千位取1时前面三位可以从000到abc任意取后面三位可以从0000到9999任意取。贡献为(abc1) * 10^3。情况三千位数字大于1。此时千位可以取1前面三位可以从000到abc任意取后面三位可以从0000到9999任意取。贡献为(abc1) * 10^3。通过这样的分情况讨论我们就把一个对整个范围的统计转化为了对每一位上、几种固定模式的计数。而每种模式的计数只依赖于当前位的前缀数字和后缀数字的长度决定10^n的幂次。2.2 状态定义与记忆化搜索上述思路是直接推导但对于更复杂的问题例如统计范围内满足“包含偶数个5”的数字个数直接推导公式会异常复杂。这时我们引入记忆化搜索来实现动态规划。我们定义一个DFS函数dfs(int pos, int cnt, bool limit, bool lead)。pos: 当前正在处理第几位从最高位向最低位处理。cnt: 一个状态变量表示到当前位置为止我们关心的统计信息。例如在统计数字k出现次数时cnt可以表示已经出现了几个k在统计“包含偶数个5”的问题中cnt可以是一个布尔值或整数表示当前已遇到5的个数的奇偶性。limit: 一个布尔值表示当前位是否受到原数字n的限制。如果limit为true那么当前位能填的数字最大不能超过n在这一位的值如果为false则可以填0-9。lead: 一个布尔值表示当前位是否是前导零。处理前导零对于统计数字0的出现次数至关重要因为数字0012我们通常认为是12前面的0不应该被计入0的出现次数。记忆化数组dp[pos][cnt]的含义是在不受限制limitfalse且leadfalse因为前导零状态会影响后续计数的情况下从第pos位开始在状态为cnt的条件下后续所有位能构成的、满足条件的数字总数或总贡献。通过记忆化我们避免了大量重复的子问题计算。注意limit和lead这两个参数通常不进入记忆化数组。因为limittrue意味着当前路径受到原始数字上界的约束这种情况是唯一的无法被复用。lead为true时表示还在处理前导零此时的计数逻辑和正常位不同也不能简单复用。3. 核心细节解析与实操要点理解了核心思想我们进入实现环节。这里以经典的**“计数问题”**为例给定两个整数a和b求a到b之间所有数字中0~9每个数字出现的次数。我们将实现一个函数countDigit(int n, int x)用于统计1到n中数字x出现的次数。最终答案就是countDigit(b, x) - countDigit(a-1, x)。3.1 数位拆分与预处理第一步需要把数字n的每一位拆分开来方便我们按位处理。vectorint digits; while (n) { digits.push_back(n % 10); n / 10; } reverse(digits.begin(), digits.end()); // 使得digits[0]是最高位 int len digits.size();同时我们通常需要预处理10的幂次因为在分情况讨论时频繁用到10^i。vectorlong long power10(len 1, 1); for (int i 1; i len; i) { power10[i] power10[i - 1] * 10; }3.2 分情况讨论的实现细节我们实现一个函数countDigitByPos(int n, int x)它直接使用推导公式计算数字x在1到n中出现的次数。这是理解数位DP本质的最佳方式。以统计数字1在abcdefg中出现的次数为例我们遍历每一位i从最高位len-1到最低位0left n / power10[i1]当前位左边的数字right n % power10[i]当前位右边的数字cur (n / power10[i]) % 10当前位的数字然后针对当前位cur与x的关系进行判断cur x: 贡献为left * power10[i]cur x: 贡献为left * power10[i] right 1cur x: 贡献为(left 1) * power10[i]这里有一个极其关键的边界情况当x 0时。我们不能有前导零所以当统计数字0时最高位i len-1不能是0并且当cur 0时左边的数字left实际上不能从0开始取而要从1开始。因此对于x 0公式需要调整cur 0: 贡献为(left - 1) * power10[i] right 1cur 0: 贡献为left * power10[i]当cur 0时不可能因为数字是非负的。实际上对于x0cur只会是0或大于0。实操心得很多人在实现“计数问题”时会尝试用一个统一的公式覆盖x0和x0的情况这很容易出错。我个人的经验是将x0的情况单独处理逻辑会更清晰代码也更不容易出错。先写出x0的通用逻辑再特判x0并仔细推导x0时的公式。3.3 记忆化搜索模板解析对于更一般的数位DP问题比如求区间内“不含4”且“不含62”的数字个数记忆化搜索是更强大的工具。这里给出一个通用模板的框架用于解决“统计区间内满足某种条件的数字个数”问题。class DigitDP { private: vectorint digits; // dp[pos][state] 记忆化数组state根据具体问题定义 // 例如state可以表示已经包含特定数字的个数、前一位的数字是什么、当前数字模某个数的余数等。 // 维度大小取决于状态定义这里用-1初始化表示未计算。 vectorvectorint dp; // 核心DFS函数 // pos: 当前处理位从0开始0是最高位 // state: 当前状态 // limit: 是否受到上界限制 // lead: 是否是前导零 int dfs(int pos, int state, bool limit, bool lead) { // 递归边界所有位都处理完毕 if (pos digits.size()) { // 根据最终state判断是否得到一个合法数字返回1或0 // 例如求不含4的数字个数这里总是返回1只要成功构造到底 // 例如求数字1出现的次数这里需要返回state即累计的计数 // 这是一个需要根据具体问题填充的“出口条件”。 return check(state) ? 1 : 0; } // 记忆化只有在无限制且无前导零时才能复用 if (!limit !lead dp[pos][state] ! -1) { return dp[pos][state]; } int upper limit ? digits[pos] : 9; // 当前位能取的最大值 int lower lead ? 0 : 0; // 当前位能取的最小值通常为0但受lead影响 // 注意有时前导零状态下当前位也可以从1开始这取决于问题定义。 int res 0; for (int d lower; d upper; d) { // 根据当前选择的数字d更新状态new_state // 例如如果统计数字k的出现次数则 new_state state (d k) // 例如如果限制不能有4则 if(d4) continue; // 例如如果限制不能有连续的62则 if(state6 d2) continue; int new_state updateState(state, d, lead); bool new_limit limit (d upper); bool new_lead lead (d 0); res dfs(pos 1, new_state, new_limit, new_lead); } // 记录状态同样只在无限制且无前导零时记录 if (!limit !lead) { dp[pos][state] res; } return res; } // 辅助函数根据具体问题实现 bool check(int state) { /* ... */ } int updateState(int old_state, int digit, bool lead) { /* ... */ } public: // 初始化将数字n分解为数位数组 void init(int n) { digits.clear(); while (n) { digits.push_back(n % 10); n / 10; } reverse(digits.begin(), digits.end()); dp.assign(digits.size(), vectorint(/*状态空间大小*/, -1)); } // 对外接口计算[1, n]中满足条件的数字个数 int solve(int n) { init(n); // 初始状态从最高位开始初始状态为0受到限制处于前导零状态。 return dfs(0, 0, true, true); } };这个模板是解决数位DP问题的“瑞士军刀”。state的定义是整个问题的灵魂它需要精确地刻画到当前位置为止所有影响后续决策的信息。check和updateState函数则是填充具体问题逻辑的地方。4. 实操过程以“计数问题”为例的完整实现现在我们结合分情况讨论和记忆化搜索两种思路给出“计数问题”的完整C实现。我们将实现两种方法以作对比。4.1 方法一直接分情况讨论公式法这种方法高效且直观特别适合“统计单个数字出现次数”这类问题。#include iostream #include vector #include algorithm using namespace std; // 计算10的幂 long long power10(int x) { long long res 1; while (x--) res * 10; return res; } // 统计1~n中数字x出现的次数 (x 属于 0~9) long long countDigit(long long n, int x) { if (n 0) return 0; vectorint digits; long long t n; while (t) { digits.push_back(t % 10); t / 10; } reverse(digits.begin(), digits.end()); // digits[0]是最高位 long long res 0; int len digits.size(); // 从最高位遍历到最低位 for (int i 0; i len; i) { int left 0, right 0, cur digits[i]; long long pow_i power10(len - i - 1); // 当前位权重10^(len-i-1) // 计算左边数字 for (int j 0; j i; j) left left * 10 digits[j]; // 计算右边数字 for (int j i 1; j len; j) right right * 10 digits[j]; if (x ! 0) { // 情况1当前位数字小于x if (cur x) { res left * pow_i; } // 情况2当前位数字等于x else if (cur x) { res left * pow_i right 1; } // 情况3当前位数字大于x else { res (left 1) * pow_i; } } else { // 特判数字0需要排除前导零的情况 // 当前位是0 if (cur 0) { // 左边部分不能全为0所以是(left - 1) // 注意当left为0时表示当前位是最高位且为0这不可能在1~n的统计中发生因为n1。 // 但为了公式通用我们这样写实际上在循环中当i是最高位且cur0时left0此项贡献为负会被后续逻辑处理吗 // 更安全的写法是 res (left - 1) * pow_i right 1; // 但需要处理left为0的情况。实际上当统计0时最高位不可能为0除非n0已排除。 // 所以我们可以加一个判断if (left 0) // 一个更清晰的实现如下 if (left 0) { res (left - 1) * pow_i right 1; } else { // left 0说明当前位是最高位且为0这种情况不应该被统计是前导零 // 实际上在1~n的统计中最高位不会是0所以这个分支不会进入。 // 但为了逻辑完整我们什么也不加。 } } else { // 当前位大于0 res left * pow_i; } } } return res; } int main() { long long a, b; while (cin a b, a || b) { if (a b) swap(a, b); for (int x 0; x 9; x) { long long cnt countDigit(b, x) - countDigit(a - 1, x); cout cnt (x 9 ? \n : ); } } return 0; }代码要点解析power10函数用于快速计算10^i避免在循环中重复计算。countDigit函数是核心。它遍历每一位根据当前位cur与目标数字x的关系应用我们推导的公式。对于x 0的特判我们采用了更清晰的写法先判断cur 0再在内部判断left 0。这避免了(left - 1)可能为负数的情况逻辑更鲁棒。main函数中通过countDigit(b, x) - countDigit(a-1, x)得到区间[a, b]的统计结果。输入以0 0结束是这类题目的常见格式。4.2 方法二记忆化搜索实现虽然对于“计数问题”公式法更优但为了展示模板的用法我们也可以用记忆化搜索实现。这里状态state直接定义为当前已统计到的数字x的个数。#include iostream #include cstring #include vector using namespace std; int x; // 要统计的目标数字 vectorint digits; int dp[20][20]; // dp[pos][cnt] 记忆化数组 // pos: 当前位cnt: 当前已统计到的数字x的个数limit: 是否受限lead: 前导零 int dfs(int pos, int cnt, bool limit, bool lead) { if (pos digits.size()) { // 递归到底返回统计到的个数 return cnt; } if (!limit !lead dp[pos][cnt] ! -1) { return dp[pos][cnt]; } int upper limit ? digits[pos] : 9; int lower 0; int res 0; for (int d lower; d upper; d) { int new_cnt cnt; if (!lead || d ! 0) { // 如果不是前导零状态或者当前位不是0针对x0的情况 if (d x) { new_cnt; } } else { // 是前导零且当前位是0这个0不计入统计 } bool new_limit limit (d upper); bool new_lead lead (d 0); res dfs(pos 1, new_cnt, new_limit, new_lead); } if (!limit !lead) { dp[pos][cnt] res; } return res; } long long countDigitDFS(long long n, int target) { if (n 0) return 0; x target; digits.clear(); long long t n; while (t) { digits.push_back(t % 10); t / 10; } reverse(digits.begin(), digits.end()); memset(dp, -1, sizeof dp); // 注意初始状态cnt0, limittrue, leadtrue return dfs(0, 0, true, true); } int main() { long long a, b; while (cin a b, a || b) { if (a b) swap(a, b); for (int x 0; x 9; x) { long long cnt countDigitDFS(b, x) - countDigitDFS(a - 1, x); cout cnt (x 9 ? \n : ); } } return 0; }两种方法对比公式法思路直接代码稍复杂尤其是处理x0但运行效率极高是解决此类特定问题的首选。记忆化搜索法代码结构清晰、模板化更容易扩展到更复杂的问题如求数字和、求特定序列个数等但运行效率略低于公式法因为存在递归开销和状态存储。实操心得在竞赛或面试中如果明确是“统计数字出现次数”问题优先使用公式法它更快且不易写错。如果问题是更一般的“满足某种条件的数字个数”那么记忆化搜索模板是唯一的选择。平时练习时建议两者都掌握公式法锻炼推导能力模板法锻炼抽象和建模能力。5. 常见问题与排查技巧实录数位DP思路巧妙实现时细节繁多极易出错。下面是我在学习和实践中总结的几个典型“坑点”及解决方法。5.1 问题一统计数字0时结果错误这是最常见的问题。很多人会把x0和x0的公式混用导致多算或少算。排查与解决理解根源数字0不能出现在最高位前导零。在公式法中这意味着当cur 0时左边的数字left不能取0否则整个数字就是前导零开头的。因此贡献是(left - 1) * power10[i] right 1并且需要保证left 0。调试方法用小的测试用例手动验证。例如计算countDigit(10, 0)。正确结果应该是1数字10包含一个0。如果你的程序返回2那很可能把1前面的那个“隐式的”前导零也算进去了。代码检查确保你的代码中有对x 0的独立分支并且在这个分支里正确处理了cur 0且left 0的情况即当前位是最高位且为0应跳过。5.2 问题二记忆化搜索时状态设计错误导致重复计算或漏算记忆化搜索的核心是dp数组的定义。如果状态state设计得不完整就会导致不同的路径错误地共享了同一个dp值。排查与解决问自己到当前位置pos为止哪些信息会影响后续位的选择这些信息都必须包含在state里。示例1统计数字k出现次数只需要记录已经出现的k的个数 (cnt)。因为后续无论怎么填只需要在最终结果上加上当前的cnt。示例2不含62需要记录前一位数字是否是6。因为如果前一位是6那么当前位就不能填2。示例3数字之和模7等于0需要记录当前已构造数字的各数位和模7的值 (sum_mod)。检查limit和lead牢记limit和lead不参与记忆化。只有当!limit !lead时dp[pos][state]才是通用的可以被后续搜索复用。在记忆化和读取记忆化结果时必须加上这个条件判断。使用打印调试在DFS函数开头打印pos,state,limit,lead和当前计算的结果。观察在!limit !lead的情况下相同的(pos, state)是否返回了相同的值。如果不一致说明状态设计有误。5.3 问题三区间边界处理错误题目要求统计[a, b]的范围我们通常转化为count(b) - count(a-1)。这里有两个易错点a可能为0或1我们的count(n)函数通常统计的是1 ~ n。如果a 0那么a-1 -1传入函数会导致错误。需要特判或者设计count(n)函数能处理n0的情况通常0中不含任何数字所有计数为0。数据溢出a和b的范围可能很大比如10^18使用int会溢出。务必使用long long。解决方案long long countDigit(long long n, int x) { if (n 0) return 0; // 处理 n0 或 n-1 的情况 // ... 正常计算 } // 在主函数中 long long ans countDigit(b, x) - countDigit(a - 1, x); // 如果 a 可能为1 a-10被上面函数处理为0是安全的。5.4 问题四递归深度与栈溢出数位DP的递归深度等于数字的位数对于long long范围内的数最多19位10^18递归深度很小通常不会栈溢出。但在一些在线判题系统或特殊环境下如果递归函数内局部变量过多或开了大数组可能会有风险。优化建议将记忆化数组dp定义为全局变量或静态变量避免在递归栈中分配。确保DFS函数的参数尽可能使用基本类型避免传递大的结构体。如果确实担心可以将递归改为迭代但数位DP的迭代写法比递归复杂得多可读性差非必要不推荐。5.5 记忆化搜索模板的初始化与多次查询我们的模板中dp数组和digits数组是针对一个特定的n进行初始化的。如果题目需要多次查询不同的n必须在每次调用solve(n)前重新初始化digits和dp数组。最佳实践 将DigitDP类实例化每次查询时DigitDP solver; int ans1 solver.solve(n1); int ans2 solver.solve(n2); // 注意solver内部会重新init(n2)或者在solve函数内部一开始就调用init(n)。数位统计DP是动态规划皇冠上的一颗明珠它将复杂的区间计数问题优雅地分解为数位上的独立决策。掌握它不仅能让你在竞赛中解决一大类难题更能深刻理解“状态”和“记忆化”这两个动态规划的核心概念。从“计数问题”这个经典例题入手先吃透分情况讨论的公式推导再熟练运用记忆化搜索的通用模板逐步挑战更复杂的变种问题如Windy数、不要62等你的DP功力必将更上一层楼。在调试时耐心地用小数据推演厘清limit和lead的作用是通往AC的必经之路。