数位 DP 是一类统计满足某条件的数的个数的动态规划方法。核心思路是将数字拆成各位，从高位到低位逐位决策，用"是否紧贴上限"作为状态。
一、适用场景
Mermaid · 渲染中（下方为源码）
graph TD A[数位DP] --> B[拆数字各位] B --> C[高位到低位决策] C --> D[状态: 紧贴上限?]
- 求 [L, R] 中满足某性质的整数个数
- 性质与"各位数字"相关（如：不含 4、各位之和为 k、相邻位不等）
- 数据范围通常 10⁹ ~ 10¹⁸，无法枚举
二、通用模板（记忆化搜索）
// 模板：统计 [0, n] 中满足条件的数的个数
public int countNumbers(int n) {
char[] digits = String.valueOf(n).toCharArray();
int len = digits.length;
int[][] memo = new int[len][/* 状态维度 */];
for (int[] row : memo) Arrays.fill(row, -1);
return dfs(digits, 0, /* 初始状态 */, true, memo);
}
// pos: 当前处理到第几位
// state: 题目相关状态（如前一位数字、数字和等）
// tight: 是否受上限约束
int dfs(char[] digits, int pos, int state, boolean tight, int[][] memo) {
if (pos == digits.length) return 1; // 成功构造一个数
if (!tight && memo[pos][state] != -1) return memo[pos][state];
int limit = tight ? digits[pos] - '0' : 9;
int count = 0;
for (int d = 0; d <= limit; d++) {
// 剪枝：跳过不合法的数字
if (!isValid(d, state)) continue;
int nextState = transition(state, d);
count += dfs(digits, pos + 1, nextState, tight && (d == limit), memo);
}
if (!tight) memo[pos][state] = count;
return count;
}