引言
在算法竞赛中，我们经常遇到一类问题：给定一个区间 [L,R][L,R]，统计其中满足某种条件的整数个数。条件可能是“数字中不能出现 4”、“相邻两位之差至少为 2”，或者“统计每个数码出现的次数”。当区间范围大到 10181018 甚至 1010010100 时，暴力枚举显然不可行。
数位 DP（Digit DP）正是为解决这类问题而生的。它的核心思想是：按位构造——从最高位到最低位一位一位地“拼”出数字，在拼的过程中进行动态规划。由于同一状态会被多次遇到，我们使用记忆化搜索来避免重复计算。
如果说暴力枚举是“从 1 数到 n，一个一个检查”，那么数位 DP 就是“像搭积木一样逐位组装数字，用记忆化跳过重复的组装过程”——它把 O(n)O(n) 的枚举优化到了 O(logn)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(nlogn)O(nlogn)。当 n=109n=109 时，显然无法接受。
观察计数过程：从 7000 数到 7999、从 8000 数到 8999、从 9000 数到 9999，后三位都是从 000 变到 999，过程完全一样，只有千位不同。数位 DP 正是利用这种重复性：把“后三位从 000 到 999 的计数”预处理好，存到一个通用数组中，高位枚举时直接复用。
1.2 按位枚举
数位 DP 通常从最高位开始枚举每一位可以填的数字。例如，统计 [1,n][1,n] 中不含 4 的数字个数，设 n=3456n=3456：
第 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/false |
lead | 当前是否处于前导零状态 | 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(logn×S)O(logn×S)，其中 SS 是状态数 |
| 空间复杂度 | O(logn×S)O(logn×S) |
| 适用数据范围 | nn 可达 10181018 甚至 1010010100（需要用字符串存储） |
| 核心技巧 | 前缀和相减、记忆化搜索、状态压缩 |
| 常见条件 | 不含某数字、相邻数字差限制、数字和限制、回文数等 |
第四章：例题与详细解析
例题1：Windy数 —— 洛谷 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 数个数：
cpp
for (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][last+2] != -1) return dp[pos][last+2]; 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][last+2] = 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]。
状态设计：抓住题目条件的本质，设计合适的状态维度。
记忆化：只有不受限制且非前导零的状态才能复用。
从 P2657（Windy数）的“相邻差限制”到 P2602（数字计数）的“统计每个数码出现次数”，数位 DP 的套路高度统一：写一个dfs(pos, state, limit, lead)，在枚举当前位数字时进行条件判断。掌握这个模板，你就能应对绝大多数数位 DP 题目。
