数位 DP：按数字位统计范围内的合法数量
讲清 pos、tight、started 和业务状态，使用记忆化搜索统计范围内满足条件的数字数量。
知识目录数据结构与算法：从基础到工程实践34 / 77
“数位 DP：按数字位统计范围内的合法数量”这一块，我曾经有一种很典型的错觉：内容看懂了，自己也会了。我真正关掉答案后才发现：数位 DP 是我看题解也容易迷路的一类题，尤其是前导零、上界限制和记忆化状态，经常少一个条件就算错。后来我用画图、手算和最小代码反复验证，才把表面的熟悉变成可以复述的理解。
数位 DP 用来统计某个范围内满足条件的数字数量，比如 1..n 中不含某个数字的数、有多少个数字包含重复位、数字之和满足条件的个数。
数位 DP 解决什么问题
普通枚举 1..n 在 n 很大时不可行。数位 DP 不枚举每个数字，而是从高位到低位决定每一位可以放什么。
图：tight 表示当前前缀是否仍然贴着上界
核心状态
数位 DP 常见参数：
pos：当前处理到第几位。tight：前面位是否都贴着上界。started：是否已经开始放非前导零数字。- 业务状态：比如数字和、是否出现某个数字、使用过的数字集合。
例子：统计不含数字 4 的数量
class DigitDP {
char[] digits;
Integer[][] memo;
int countWithoutFour(int n) {
digits = String.valueOf(n).toCharArray();
memo = new Integer[digits.length][2];
return dfs(0, true, false);
}
int dfs(int pos, boolean tight, boolean started) {
if (pos == digits.length) {
return started ? 1 : 0;
}
if (!tight && memo[pos][started ? 1 : 0] != null) {
return memo[pos][started ? 1 : 0];
}
int limit = tight ? digits[pos] - '0' : 9;
int ans = 0;
for (int d = 0; d <= limit; d++) {
if (d == 4) continue;
boolean nextStarted = started || d != 0;
boolean nextTight = tight && d == limit;
ans += dfs(pos + 1, nextTight, nextStarted);
}
if (!tight) memo[pos][started ? 1 : 0] = ans;
return ans;
}
}
真实写法里，memo 的维度要包含所有会影响未来决策的状态。
为什么 tight 不能随便缓存
如果 tight=true，当前位置能选的最大数字受上界限制。不同上界前缀下，结果不同，所以通常只缓存 tight=false 的状态。
处理区间 [L, R]
数位 DP 常用技巧是把区间问题变成前缀问题：
answer(L, R) = count(0, R) - count(0, L - 1)
这样只需要写一个 count(n)。
我的分析
数位 DP 看起来抽象，但其实就是“按位构造数字”。它适合范围巨大但位数有限的问题，比如 10^18 也只有 19 位。关键是状态维度不能漏：如果题目限制数字不能重复，就需要 mask；如果限制数字和，就要记录 sum。
面试题
- 数位 DP 中
tight表示什么？ - 为什么通常只缓存
tight=false的状态？ - 前导零为什么需要单独处理？
- 区间
[L, R]为什么可以转成两个前缀计数？ - 数位 DP 适合什么规模的问题？
JARVIS · 当前文章
有哪里没看懂？可以只问这篇。
Jarvis 会限定在《数位 DP：按数字位统计范围内的合法数量》及其公开关联内容中检索，并把引用定位回原文章节。