区间 [1,n] 里 n 可能大到 10¹⁸，没法逐个枚举——按数字的每一位逐位确定，配合记忆化搜索，直接统计满足条件的数有多少个。
有一类问题：统计区间 [1, n] 里，有多少个数满足某种"数位上的条件"（比如"不包含数字 4"、"各位数字之和是 3 的倍数"）。如果 n 不大，直接从 1 枚举到 n 逐个检查就行；但如果 n 大到 10¹⁸ 这种量级，逐个枚举根本不可能在合理时间内跑完。数位 DP 不去枚举每一个具体的数，而是按数字的每一位去构造，用动态规划统计出满足条件的数一共有多少个。
把 n 按十进制拆成一个数位数组（从最高位到最低位），从最高位开始，逐位决定当前这一位填哪个数字。核心在于一个叫 tight（"是否贴着上界"）的状态：如果前面已经填的每一位都和 n 对应位置完全相同，那么当前这一位最多只能填到 n 对应位置的数字（不能超过，否则拼出来的数会比 n 大）；只要前面某一位填得比 n 对应位置小，后面所有位就可以自由填 0~9（因为已经比 n 小了，后面无论怎么填都不会超过 n）。
| 状态 | 含义 | 这一位能填的范围 |
|---|---|---|
| tight = true | 前面每一位都和 n 对应位置一模一样 | 0 ~ n 当前这一位的数字（不能更大） |
| tight = false | 前面已经有一位比 n 对应位置小 | 0 ~ 9（自由选择） |
tight=false 之后的状态可以记忆化？一旦 tight 变成 false，剩下要填的位数、以及每一位能自由选择的范围（0~9）就完全和 n 具体是多少无关了——只取决于"还剩几位没填"。这正是 12.4 节记忆化搜索的应用场景：只要"剩余位数"相同，tight=false 情况下能凑出的合法方案数一定相同，可以把结果缓存起来，不用重复计算。tight=true 的状态因为全程只有唯一一条路径（贴着 n 走），不会重复出现，不需要缓存。以"统计 [1,23] 中不包含数字 4 的数有多少个"为例。先转换成更容易处理的形式：设 f(n) 表示 [0,n] 中不含数字 4 的数的个数（把 0 也算进去，因为 0 本身不含 4，方便统一处理前导零），那么 [1,n] 里的答案就是 f(n) - 1（减掉多算的 0）。n=23，按位拆成 [2, 3]：
| 十位填 | 是否等于上界 2 | 下一状态 |
|---|---|---|
| 0 | 否（0<2） | dp(pos=1, tight=false) |
| 1 | 否（1<2） | dp(pos=1, tight=false) |
| 2 | 是（2=2） | dp(pos=1, tight=true) |
4（超过上界 2 也不行），可选 0、1、2 三种，其中 0、1 都比上界小，之后个位可以自由填；只有填 2（贴着上界）时，个位仍然要受 n 的个位 3 限制。| 状态 | 个位能填的范围 | 排除数字 4 | 方案数 |
|---|---|---|---|
| dp(1, tight=false) | 0~9（自由） | 去掉 4，剩 9 种 | 9 |
| dp(1, tight=true) | 0~3（贴着上界 3） | 0,1,2,3 都不是 4 | 4 |
dp(0,true) = 2 × dp(1,false) + dp(1,true) = 2×9 + 4 = 22——十位填 0 或 1 各贡献 9 种方案（来自两条独立的 tight=false 分支，但因为状态相同，只需要真正计算一次，第二次直接查缓存），十位填 2 贡献 4 种方案。f(23)=22，最终 [1,23] 的答案是 22-1=21——和直接列出 1~23、数出"不含 4"的个数（排除掉 4 和 14 这两个数，23-2=21）完全一致。| 1 | int digits[20], len; // digits：n 按位拆解后的数组（从高位到低位） |
| 2 | long long memo[20]; // memo[pos]：tight=false 时，从 pos 开始还能凑出多少种方案（-1 表示未算过） |
| 3 | |
| 4 | long long DFS(int pos, bool tight) |
| 5 | { |
| 6 | if (pos == len) return 1; // 所有位都填完了，凑出了一个合法的数 |
| 7 | if (!tight && memo[pos] != -1) return memo[pos]; // ★ 只有 tight=false 才查缓存 |
| 8 | |
| 9 | int upper = tight ? digits[pos] : 9; // 贴着上界就只能填到 n 当前这一位；否则自由填到 9 |
| 10 | long long res = 0; |
| 11 | for (int d = 0; d <= upper; d++) |
| 12 | { |
| 13 | if (d == 4) continue; // 题目条件：不能出现数字 4 |
| 14 | res += DFS(pos + 1, tight && (d == upper)); // 只有"贴着上界" 且 "填的正好是上界数字" 才继续贴着 |
| 15 | } |
| 16 | |
| 17 | if (!tight) memo[pos] = res; // ★ 只缓存 tight=false 的结果 |
| 18 | return res; |
| 19 | } |
| 20 | |
| 21 | long long CountNoFour(long long n) // 统计 [1,n] 中不含数字 4 的个数 |
| 22 | { |
| 23 | len = 0; |
| 24 | while (n > 0) { digits[len++] = n % 10; n /= 10; } |
| 25 | reverse(digits, digits + len); // 变成从高位到低位 |
| 26 | memset(memo, -1, sizeof(memo)); |
| 27 | return DFS(0, true) - 1; // -1：减掉多算的数字 0 |
| 28 | } |
(pos, tight)，而且只有 tight=false 时才值得缓存（tight=true 的状态在整个递归过程中，对每个 pos 最多只会经过一次，缓存它没有意义）。状态数是 O(位数)（tight=false 时每个 pos 只算一次），每个状态枚举 0~9 共 10 种选择，整体复杂度大约是 O(位数 × 10)——即使 n 大到 10¹⁸（19 位），也只需要几百次计算，远比逐个枚举快得多。
tight=true 的结果也存进 memo[pos]，会和 tight=false 的正确结果互相覆盖、污染——因为同一个 pos，tight=true 和 tight=false 对应的"能填的范围"通常不同，答案也不同，混在一起会导致后续查询用错缓存。[1,n] 这种从 1 开始的区间。如果题目要求的是任意区间 [l,r]，标准做法是分别计算 CountNoFour(r) 和 CountNoFour(l-1)，再相减——这一点和 5.1 节前缀和的思路是一致的：[l,r] 的答案 = f(r) - f(l-1)。(pos, tight) 就够了，因为"是否含 4"只看当前这一位本身。如果题目条件涉及"目前为止的数字和"、"上一位填的是什么数字"这类需要额外记忆的信息，状态要相应增加维度，比如 dp[pos][tight][目前数字和]，思路不变，但状态设计需要根据具体条件调整。