引言在算法竞赛中我们经常遇到一类问题给定一个区间 [L,R][L,R]统计其中满足某种条件的整数个数。条件可能是“数字中不能出现 4”、“相邻两位之差至少为 2”或者“统计每个数码出现的次数”。当区间范围大到 10181018 甚至 1010010100 时暴力枚举显然不可行。数位 DPDigit DP正是为解决这类问题而生的。它的核心思想是按位构造——从最高位到最低位一位一位地“拼”出数字在拼的过程中进行动态规划。由于同一状态会被多次遇到我们使用记忆化搜索来避免重复计算。如果说暴力枚举是“从 1 数到 n一个一个检查”那么数位 DP 就是“像搭积木一样逐位组装数字用记忆化跳过重复的组装过程”——它把 O(n)O(n) 的枚举优化到了 O(log⁡n)O(logn) 的量级。前置知识在学习数位 DP 之前你需要掌握以下基础数位一个数字的每一位。例如数字 1234 的数位是 1、2、3、4。前缀和思想统计 [L,R][L,R] 内的答案转化为 [1,R][1,R] 的答案减去 [1,L−1][1,L−1] 的答案。记忆化搜索将已经计算过的状态缓存起来下次遇到时直接复用。位运算基础虽然数位 DP 不一定用到位运算但理解二进制表示有助于理解某些变种。第一章数位DP的核心思想1.1 从暴力到数位DP考虑一个简单问题统计 [1,n][1,n] 中不含数字 4 的整数个数。暴力做法是从 1 到 n 逐个检查复杂度 O(nlog⁡n)O(nlogn)。当 n109n109 时显然无法接受。观察计数过程从 7000 数到 7999、从 8000 数到 8999、从 9000 数到 9999后三位都是从 000 变到 999过程完全一样只有千位不同。数位 DP 正是利用这种重复性把“后三位从 000 到 999 的计数”预处理好存到一个通用数组中高位枚举时直接复用。1.2 按位枚举数位 DP 通常从最高位开始枚举每一位可以填的数字。例如统计 [1,n][1,n] 中不含 4 的数字个数设 n3456n3456第 1 位千位可以填 0、1、2、3不能超过 3。填 0 时后三位任意000~999填 1、2 时同理填 3 时需要继续看下一位。第 2 位百位如果千位填了 3百位可以填 0、1、2、3、4但不能超过 4……依此类推。1.3 状态设计数位 DP 的状态通常包含以下几个维度状态维度含义典型取值pos当前处理到第几位从高位到低位state与条件相关的状态信息前一位数字、是否已经出现过某个数字等limit当前是否受到上界限制true/falselead当前是否处于前导零状态true/false前导零leading zero是指数字前面的 0例如数字 5 在 4 位数中写作 0005其中的 0 就是前导零。前导零在某些问题中需要特殊处理。第二章记忆化搜索实现2.1 模板框架数位 DP 最常用的实现方式是记忆化搜索。以下是一个通用的模板框架typedef long long ll; int digit[20]; // 存储 n 的每一位 ll dp[20][state][2]; // 记忆化数组 // pos: 当前处理到第几位从高位到低位 // state: 当前状态根据题目定义 // limit: 当前是否受到上界限制 // lead: 当前是否处于前导零状态 ll dfs(int pos, int state, bool limit, bool lead) { if (pos 0) return 1; // 已经处理完所有位返回 1表示这是一个合法数字 if (!limit !lead dp[pos][state] ! -1) return dp[pos][state]; // 记忆化只有不受限制且不是前导零时才能复用 int up limit ? digit[pos] : 9; // 当前位能填的最大数字 ll ans 0; for (int i 0; i up; i) { // 根据题目条件判断 i 是否合法 if (!valid(i, state, lead)) continue; ans dfs(pos - 1, new_state, limit (i up), lead (i 0)); } if (!limit !lead) dp[pos][state] ans; return ans; } ll solve(ll x) { if (x 0) return 0; int len 0; while (x) { digit[len] x % 10; x / 10; } memset(dp, -1, sizeof(dp)); return dfs(len, init_state, true, true); }关键点limit参数控制当前位是否能自由填 0~9。如果limit true当前位不能超过digit[pos]否则可以填 0~9。lead参数控制前导零。当lead true且当前填 0 时下一位仍然处于前导零状态。记忆化的前提是!limit !lead因为受限制或前导零的状态不是“通用”的不能复用。2.2 两种实现方式对比实现方式优点缺点记忆化搜索代码清晰、易于扩展、不易出错递归有栈开销循环递推常数小、无递归代码复杂、状态设计困难OI Wiki 指出统计答案可以选择记忆化搜索也可以选择循环迭代递推。对于初学者强烈推荐记忆化搜索因为它更直观、更容易调试。第三章性质与复杂度性质说明时间复杂度O(位数×状态数×10)O(位数×状态数×10)通常为 O(log⁡n×S)O(logn×S)其中 SS 是状态数空间复杂度O(log⁡n×S)O(logn×S)适用数据范围nn 可达 10181018 甚至 1010010100需要用字符串存储核心技巧前缀和相减、记忆化搜索、状态压缩常见条件不含某数字、相邻数字差限制、数字和限制、回文数等第四章例题与详细解析例题1Windy数 —— 洛谷 P2657题目描述Windy 定义了一种 Windy 数不含前导零且相邻两个数字之差至少为 2的正整数被称为 Windy 数。给定 AA 和 BB求 [A,B][A,B] 中 Windy 数的个数。输入示例1 10输出示例9解题思路这是一道经典的数位 DP 模板题。核心状态是上一位填了什么数字因为判断当前位是否合法需要知道上一位的值。详细解析第一步状态设计pos当前处理到第几位last上一位填的数字用-2表示初始状态确保最高位没有限制limit是否受上界限制lead是否处于前导零状态第二步预处理非必须但可以加速也可以用递推预处理 f[i][j]f[i][j] 表示长度为 ii、最高位为 jj 的 Windy 数个数cppfor (int i 0; i 9; i) f[1][i] 1; // 1 位数都是 Windy 数 for (int len 2; len 10; len) { for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (abs(i - j) 2) f[len][i] f[len-1][j]; } } }第三步记忆化搜索实现ll dfs(int pos, int last, bool limit, bool lead) { if (pos 0) return 1; if (!limit !lead dp[pos][last2] ! -1) return dp[pos][last2]; int up limit ? digit[pos] : 9; ll ans 0; for (int i 0; i up; i) { if (!lead abs(i - last) 2) continue; // 非前导零时检查差值 ans dfs(pos - 1, i, limit (i up), lead (i 0)); } if (!limit !lead) dp[pos][last2] ans; return ans; }第四步答案计算ll solve(ll x) { if (x 0) return 0; int len 0; while (x) { digit[len] x % 10; x / 10; } memset(dp, -1, sizeof(dp)); return dfs(len, -2, true, true); } // 主函数 cout solve(R) - solve(L - 1) endl;时间复杂度O(位数×10×状态数)≈O(10×10×2)O(200)O(位数×10×状态数)≈O(10×10×2)O(200) 每次查询。例题2数字计数 —— 洛谷 P2602题目描述给定两个正整数 aa 和 bb求在 [a,b][a,b] 中的所有整数中每个数码0~9各出现了多少次。输入示例1 99输出示例9 20 20 20 20 20 20 20 20 20解题思路需要对 0~9 每个数码分别做一次数位 DP。状态设计为当前已经统计的该数码出现了多少次。详细解析第一步状态设计pos当前处理到第几位cnt当前数码已经出现的次数limit是否受上界限制lead是否处于前导零状态统计 0 时需要特殊处理第二步记忆化搜索实现ll dfs(int pos, int cnt, bool limit, bool lead, int target) { if (pos 0) return cnt; if (!limit !lead dp[pos][cnt] ! -1) return dp[pos][cnt]; int up limit ? digit[pos] : 9; ll ans 0; for (int i 0; i up; i) { int add 0; if (!(lead i 0) i target) add 1; // 非前导零且等于目标数码 ans dfs(pos - 1, cnt add, limit (i up), lead (i 0), target); } if (!limit !lead) dp[pos][cnt] ans; return ans; }第三步处理前导零统计数码 0 时前导零不能计入。例如数字 5 在 3 位数中写作 005前面的两个 0 不应被统计。上面的代码通过lead i 0判断是否为前导零如果是则不加 1。第四步答案计算for (int target 0; target 9; target) { memset(dp, -1, sizeof(dp)); ll ansR dfs(len, 0, true, true, target); // 需要对 a-1 再做一次相减 cout ansR - ansL ; }时间复杂度O(10×位数×状态数)≈O(10×10×10)O(1000)O(10×位数×状态数)≈O(10×10×10)O(1000) 每次查询。第五章常见变体与应用场景变体核心思路典型例题不含某数字枚举时跳过该数字P2657不含前导零且相邻差≥2数字和限制状态中记录数位和求数位和能被某数整除的数回文数记录前半部分后半部分对称判断二进制数位DP按二进制位枚举不含连续 1 的个数AC自动机数位DP多模式串匹配总结数位 DP 通过逐位构造 记忆化搜索将指数级的暴力枚举优化为多项式级。它的核心在于前缀和相减[L,R][L,R] 的答案 [1,R]−[1,L−1][1,R]−[1,L−1]。状态设计抓住题目条件的本质设计合适的状态维度。记忆化只有不受限制且非前导零的状态才能复用。从 P2657Windy数的“相邻差限制”到 P2602数字计数的“统计每个数码出现次数”数位 DP 的套路高度统一写一个dfs(pos, state, limit, lead)在枚举当前位数字时进行条件判断。掌握这个模板你就能应对绝大多数数位 DP 题目。