数位DP：从“穷举数字”到“逐位拆解”

引言

在算法竞赛中，我们经常遇到一类问题：给定一个区间 [L,R][L,R]，统计其中满足某种条件的整数个数。条件可能是“数字中不能出现 4”、“相邻两位之差至少为 2”，或者“统计每个数码出现的次数”。当区间范围大到 10181018 甚至 1010010100 时，暴力枚举显然不可行。

数位 DP（Digit DP）正是为解决这类问题而生的。它的核心思想是：按位构造——从最高位到最低位一位一位地“拼”出数字，在拼的过程中进行动态规划。由于同一状态会被多次遇到，我们使用记忆化搜索来避免重复计算。

如果说暴力枚举是“从 1 数到 n，一个一个检查”，那么数位 DP 就是“像搭积木一样逐位组装数字，用记忆化跳过重复的组装过程”——它把 O(n)O(n) 的枚举优化到了 O(log⁡n)O(logn) 的量级。

前置知识

在学习数位 DP 之前，你需要掌握以下基础：

1. 数位：一个数字的每一位。例如，数字 1234 的数位是 1、2、3、4。

2. 前缀和思想：统计 [L,R][L,R] 内的答案，转化为 [1,R][1,R] 的答案减去 [1,L−1][1,L−1] 的答案。

3. 记忆化搜索：将已经计算过的状态缓存起来，下次遇到时直接复用。

4. 位运算基础：虽然数位 DP 不一定用到位运算，但理解二进制表示有助于理解某些变种。

第一章：数位DP的核心思想

1.1 从暴力到数位DP

考虑一个简单问题：统计 [1,n][1,n] 中不含数字 4 的整数个数。暴力做法是从 1 到 n 逐个检查，复杂度 O(nlog⁡n)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 的状态通常包含以下几个维度：

前导零（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 指出，统计答案可以选择记忆化搜索，也可以选择循环迭代递推。对于初学者，强烈推荐记忆化搜索，因为它更直观、更容易调试。

第三章：性质与复杂度

第四章：例题与详细解析

例题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) 每次查询。

第五章：常见变体与应用场景

总结

数位 DP 通过逐位构造 + 记忆化搜索，将指数级的暴力枚举优化为多项式级。它的核心在于：

1. 前缀和相减：[L,R][L,R] 的答案 = [1,R]−[1,L−1][1,R]−[1,L−1]。

2. 状态设计：抓住题目条件的本质，设计合适的状态维度。

3. 记忆化：只有不受限制且非前导零的状态才能复用。

从 P2657（Windy数）的“相邻差限制”到 P2602（数字计数）的“统计每个数码出现次数”，数位 DP 的套路高度统一：写一个dfs(pos, state, limit, lead)，在枚举当前位数字时进行条件判断。掌握这个模板，你就能应对绝大多数数位 DP 题目。