数位 DP（按位走上界）
动态规划 · 自由分支与贴着走 · O(位数) 数天文数字
数不过来的时候
「[1, N] 里有多少个数不含数字 4？」N=245 还能逐个检查；N=10¹⁸ 呢？数位 DP 不数「数」，改数「数位的走法」：把 N 的十进制位从高到低排开（2、4、5），想象你在一位一位地写一个 ≤ N 的数。
每一位只有两条路
自由分支：本位写得比上界位小——从此后面每一位都随便写（只避开 4，每位 9 种），一次性入账 可选数 × 9^剩余位；贴着走：本位恰写上界位数字，继续被 N 压着走。关键戏剧点：十位的上界位就是 4——想贴着走就必须写 4，被禁！tight 断裂，个位整位跳过。下表逐位记账，黄格是被加总的小计。右侧代码随每一步同步高亮。
| 位上 | 可选数 | 后缀 9^k | 小计 | |
|---|---|---|---|---|
| 百位 2 | ||||
| 十位 4 | ||||
| 个位 5 | ||||
| 合计 |
统计 [1, 245] 里不含数字 4 的数——逐个检查在 N=10¹⁸ 时爆炸。数位 DP 按位从高到低「走上界」：每位分两条路——自由分支（本位填得比上界位小，后缀彻底自由）和贴着走（恰好填上界位数字，继续受约束）
1function countNoBan(n: number, ban: number): number {
2 const ds = [...String(n)].map(Number); // 上界数位（高位在前）
3 let total = 0;
4 let tight = true; // 还贴着上界吗
5 for (let i = 0; i < ds.length && tight; i++) {
6 const free = ds.length - i - 1; // 后缀自由位数
7 let cnt = 0;
8 for (let x = 0; x < ds[i]; x++) // 本位填小于上界位的数
9 if (x !== ban) cnt++;
10 total += cnt * 9 ** free; // 每个分支后缀 9^free 种
11 if (ds[i] === ban) tight = false; // 上界位就是禁数字：断裂
12 }
13 if (tight) total += 1; // N 自身合法则计入
14 return total - 1; // 去掉 0
15}
N / 禁245 / 数字 4
tight✓（起步贴着上界）
1 / 8
通用模板
记忆化搜索版：
state 举例：前导零标记（数 0 的个数类）、上一位数字（windy 数）、模 k 余数（整除类）。
复杂度：O(位数 × 状态数 × 10)——N=10¹⁸ 也只有 19 位。
区间技巧：[L, R] 的答案 = count(R) − count(L−1)。
dp(pos, tight, state)——pos 当前位、tight 是否贴上界、state 按题意定制。state 举例：前导零标记（数 0 的个数类）、上一位数字（windy 数）、模 k 余数（整除类）。
复杂度：O(位数 × 状态数 × 10)——N=10¹⁸ 也只有 19 位。
区间技巧：[L, R] 的答案 = count(R) − count(L−1)。
「不含 62」「至少一个 1」「二进制表示里 1 比 0 多」……所有这类按数位施加约束的计数题，都是同一个走位骨架换 state。DP 大类至此十页，五种状态设计全景：序列前缀、区间、集合、树、数位——状态定义的想象力，就是动态规划的全部秘密。