数位动态规划（Digit DP）是解决”区间 [L, R] 中满足某性质的数字个数”这类计数问题的利器。它将数字按位拆分，利用前缀和思想将区间计数转化为 f(R) - f(L-1)，通过记忆化搜索高效枚举每一位的可能取值。本文用Java完整实现数位DP，覆盖基础模板到复杂条件计数。
一、问题引入：数字中的约束计数
问题：统计区间 [1, 1000000] 中，各位数字之和能被3整除的数字有多少个？
暴力枚举 O(R-L+1) 在范围大时不可行。数位DP通过按位处理，将复杂度优化到 O(log R × 状态数)。
核心思想：
– 将数字转为字符串/数组，从高到低逐位处理
– 用 tight 标记表示当前位是否受原数上界约束
– 用 dp[pos][sum][tight] 记录记忆化状态
二、基础模板：统计特定范围内数字个数
import java.util.*;
/**
* 数位DP基础模板
* 问题: 统计 [0, n] 中满足条件的数字个数
*/
public class DigitDPTemplate {
private int[] digits; // 将数字按位拆分（高位在前）
private Long[][] memo; // 记忆化数组: memo[pos][tight] -> 方案数
/**
* 统计 [0, n] 中，数字各位之和能被3整除的数字个数
*/
public long countDivisibleBy3(long n) {
if (n < 0) return 0;
digits = toDigits(n);
int len = digits.length;
// memo[pos][sum_mod_3][tight]，-1表示未计算
memo = new Long[len][3][2];
return dfs(0, 0, 1); // 从最高位开始，当前和mod3=0，受约束
}
/**
* 深度优先搜索 + 记忆化
* @param pos 当前处理到的位（0表示最高位）
* @param sumMod 当前已处理位的数字和 mod 3
* @param tight 1表示前面所有位都与n对应位相同（受约束），0表示已小于n（自由）
* @return 从当前状态出发的有效数字个数
*/
private long dfs(int pos, int sumMod, int tight) {
if (pos == digits.length) {
// 所有位处理完毕，判断最终状态是否满足条件
return sumMod == 0 ? 1 : 0;
}
if (memo[pos][sumMod][tight] != null) {
return memo[pos][sumMod][tight];
}
long res = 0;
int upperBound = tight == 1 ? digits[pos] : 9; // 当前位最大可填数字
for (int d = 0; d <= upperBound; d++) {
int newTight = (tight == 1 && d == upperBound) ? 1 : 0;
int newSumMod = (sumMod + d) % 3;
res += dfs(pos + 1, newSumMod, newTight);
}
memo[pos][sumMod][tight] = res;
return res;
}
/**
* 将数字转为位数组（高位在前）
*/
private int[] toDigits(long n) {
String s = Long.toString(n);
int[] res = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
res[i] = s.charAt(i) - '0';
}
return res;
}
/**
* 统计 [L, R] 范围内的满足条件的数字个数
*/
public long countRange(long L, long R) {
return countDivisibleBy3(R) - countDivisibleBy3(L - 1);
}
public static void main(String[] args) {
DigitDPTemplate solver = new DigitDPTemplate();
// 测试1: 小范围验证
System.out.println("=== 测试: 各位和能被3整除的数字 ===");
for (long n = 0; n <= 30; n++) {
long count = solver.countDivisibleBy3(n);
System.out.printf("[0, %2d] 中满足条件的数字个数: %d%n", n, count);
}
// 测试2: 大范围
System.out.println("\n=== 大范围测试 ===");
long L = 1, R = 1000000;
System.out.printf("[%d, %d] 中各位和能被3整除的数字个数: %d%n",
L, R, solver.countRange(L, R));
// 暴力验证小范围
System.out.println("\n=== 暴力验证 [1, 100] ===");
long brute = bruteForce(1, 100);
long dp = solver.countRange(1, 100);
System.out.printf("暴力: %d, 数位DP: %d, 一致: %s%n", brute, dp, brute == dp);
}
private static long bruteForce(long L, long R) {
long count = 0;
for (long i = L; i <= R; i++) {
long sum = 0, x = i;
while (x > 0) {
sum += x % 10;
x /= 10;
}
if (sum % 3 == 0) count++;
}
return count;
}
}
三、进阶应用：统计不含特定子串的数字
问题：统计 [L, R] 中，数字的十进制表示不包含”13″子串的数字个数。
这需要引入额外的状态来记录前缀匹配情况。
/**
* 数位DP进阶：统计不含特定子串的数字
* 使用KMP自动机思想记录当前前缀匹配状态
*/
public class DigitDPSubstring {
private int[] digits;
private Long[][][] memo; // memo[pos][kmpState][tight]
private String forbidden = "13"; // 禁止子串
private int[] kmp; // KMP的next数组
public DigitDPSubstring() {
buildKMP();
}
private void buildKMP() {
int m = forbidden.length();
kmp = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && forbidden.charAt(i) != forbidden.charAt(j)) {
j = kmp[j - 1];
}
if (forbidden.charAt(i) == forbidden.charAt(j)) {
j++;
kmp[i] = j;
}
}
}
/**
* 获取添加数字d后的新KMP状态
*/
private int transition(int state, int d) {
char c = (char)('0' + d);
while (state > 0 && c != forbidden.charAt(state)) {
state = kmp[state - 1];
}
if (c == forbidden.charAt(state)) {
state++;
}
return state;
}
public long countWithoutSubstring(long n) {
if (n < 0) return 0;
digits = toDigits(n);
int len = digits.length;
int m = forbidden.length();
memo = new Long[len][m + 1][2];
return dfs(0, 0, 1);
}
private long dfs(int pos, int state, int tight) {
// state == forbidden.length() 表示已匹配到禁止子串，此路径无效
if (state == forbidden.length()) {
return 0;
}
if (pos == digits.length) {
return 1; // 所有位处理完毕且未出现禁止子串
}
if (memo[pos][state][tight] != null) {
return memo[pos][state][tight];
}
long res = 0;
int upperBound = tight == 1 ? digits[pos] : 9;
for (int d = 0; d <= upperBound; d++) {
int newState = transition(state, d);
int newTight = (tight == 1 && d == upperBound) ? 1 : 0;
res += dfs(pos + 1, newState, newTight);
}
memo[pos][state][tight] = res;
return res;
}
private int[] toDigits(long n) {
String s = Long.toString(n);
int[] res = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
res[i] = s.charAt(i) - '0';
}
return res;
}
public long countRange(long L, long R) {
return countWithoutSubstring(R) - countWithoutSubstring(L - 1);
}
public static void main(String[] args) {
DigitDPSubstring solver = new DigitDPSubstring();
System.out.println("=== 统计不含子串\"13\"的数字 ===");
for (long n = 0; n <= 100; n++) {
long count = solver.countWithoutSubstring(n);
System.out.printf("[0, %3d] 中不含\"13\"的数字: %d%n", n, count);
}
long L = 1, R = 1000000;
System.out.printf("\n[%d, %d] 中不含\"13\"的数字个数: %d%n",
L, R, solver.countRange(L, R));
}
}
四、综合应用：windy数计数
windy数定义：相邻两位数字之差的绝对值至少为2的正整数。
/**
* windy数计数: 相邻位数字差 >= 2
*/
public class WindyNumber {
private int[] digits;
private Long[][][] memo; // memo[pos][prevDigit][tight]
public long countWindy(long n) {
if (n <= 0) return 0;
digits = toDigits(n);
int len = digits.length;
memo = new Long[len][11][2]; // prevDigit用10表示"无前一位"（首位）
return dfs(0, 10, 1);
}
private long dfs(int pos, int prev, int tight) {
if (pos == digits.length) {
return 1; // 形成一个有效数字（注意：全0的情况需要特殊处理）
}
if (memo[pos][prev][tight] != null) {
return memo[pos][prev][tight];
}
long res = 0;
int upperBound = tight == 1 ? digits[pos] : 9;
for (int d = 0; d <= upperBound; d++) {
// 处理前导零: prev=10表示还在前导零阶段
if (prev == 10) {
if (d == 0) {
// 继续保持前导零状态
res += dfs(pos + 1, 10, (tight == 1 && d == upperBound) ? 1 : 0);
} else {
// 第一个非零数字
res += dfs(pos + 1, d, (tight == 1 && d == upperBound) ? 1 : 0);
}
} else {
// 非首位，检查相邻位差
if (Math.abs(d - prev) >= 2) {
res += dfs(pos + 1, d, (tight == 1 && d == upperBound) ? 1 : 0);
}
}
}
memo[pos][prev][tight] = res;
return res;
}
private int[] toDigits(long n) {
String s = Long.toString(n);
int[] res = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
res[i] = s.charAt(i) - '0';
}
return res;
}
public long countRange(long L, long R) {
return countWindy(R) - countWindy(L - 1);
}
public static void main(String[] args) {
WindyNumber solver = new WindyNumber();
System.out.println("=== windy数计数（相邻位差>=2）===");
long[][] tests = {{1, 10}, {1, 100}, {1, 1000}, {25, 50}, {1, 1000000}};
for (long[] t : tests) {
System.out.printf("[%d, %d] 中windy数: %d%n",
t[0], t[1], solver.countRange(t[0], t[1]));
}
// 小范围验证
System.out.println("\n小范围验证 [1, 30]:");
for (int i = 1; i <= 30; i++) {
boolean isWindy = isWindyNumber(i);
System.out.printf("%2d: %s%n", i, isWindy ? "windy" : "---");
}
}
private static boolean isWindyNumber(int n) {
String s = Integer.toString(n);
for (int i = 1; i < s.length(); i++) {
if (Math.abs(s.charAt(i) - s.charAt(i-1)) < 2) {
return false;
}
}
return true;
}
}
五、数位DP的设计框架
设计数位DP问题的通用步骤：
1. 定义状态: dp[pos][state][tight]
- pos: 当前处理到第几位
- state: 与问题相关的额外状态（如数字和、前缀匹配、前一位数字等）
- tight: 是否受上界约束
2. 确定转移: 枚举当前位d的取值，更新state和tight
3. 边界条件: pos == len 时判断是否满足条件
4. 前缀和转化: f(L, R) = f(R) - f(L-1)
六、复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(log R × S × 10) | S为状态数，10为每位枚举数 |
| 空间 | O(log R × S × 2) | 记忆化数组大小 |
实际效率极高：对于 R = 10¹⁸，log R = 19，若状态数 S = 100，总计算量约 19 × 100 × 10 = 19000 次操作。
七、总结
数位DP的魅力在于将看似需要线性枚举的范围计数问题，通过”按位拆分 + 状态压缩 + 记忆化搜索”转化为对数级复杂度。其核心技巧有三：
- 前缀和转化：
[L, R] = f(R) - f(L-1) - tight标记：区分”紧贴上界”和”自由取值”两种状态
- 状态设计：根据题目条件设计合适的额外状态（和、差、匹配位置等）
掌握数位DP后，各类数字计数问题——无论是简单的整除判定，还是复杂的自动机匹配——都能迎刃而解。它是算法竞赛中范围计数的”万能钥匙”。
