动态规划进阶：数位 DP（Digit DP）与记忆化搜索模板（数字计数与无重复数字排列）-平芜编程栈

动态规划进阶：数位 DP（Digit DP）与记忆化搜索模板（数字计数与无重复数字排列）

在算法竞赛与大厂算法高频 Hard 题中，有一类题目形式极其统一、但若使用暴力循环统计必然会在 $N = 10^9 \sim 10^{18}$ 时直接超时（TLE）的经典专题：

LeetCode 233：数字 1 的个数（Number of Digit One）；
LeetCode 902：最大为 N 的数字组合；
LeetCode 1012：至少有 1 位重复的数字（Numbers With Repeated Digits）；
LeetCode 600：不含连续 1 的非负整数；
经典区间统计：求区间 $[L, R]$ 内满足特定数位约束（如各位数字之和为质数、无前导零特定数字）的正整数个数。

暴力枚举从 $L$ 循环到 $R$ 的时间复杂度为 $\mathcal{O}(R)$。
而数位动态规划（Digit DP）做出了一项极具数学美感的降维优化：
利用前缀和转化（$[L, R] = \text{solve}(R) - \text{solve}(L-1)$），并以“从高位到低位逐位填数”的记忆化搜索（DFS + Memoization）状态机，在【$\mathcal{O}(\log_{10} R)$ 对数时间】（仅需几十次常数级计算）内秒杀千亿级数字区间统计！

今天我们把数位 DP 的两大核心布尔约束（isLimit与isNum）、记忆化搜索标准状态机与万能模板彻底讲透。

一、前缀差分转化（区间 $[L, R]$ 统一化为 $[0, N]$）

根据前缀和原理，计算区间 $[L, R]$ 中满足条件的数字总数：
$$\mathbf{\text{Count}([L, R]) = \text{Count}([0, R]) - \text{Count}([0, L - 1])}$$
我们只需要设计一个函数solve(n)，专门计算在 $[0, n]$ 范围内满足条件的数字总数即可！

二、数位 DP 记忆化搜索的核心状态机与四大核心参数

我们将数字 $N$ 拆解为一个十进制字符数组 $s$（从最高位到最低位）。
定义深度优先搜索函数：
$$\mathbf{\text{dfs}(\text{index}, \text{state}, \text{isLimit}, \text{isNum})}$$

graph TD A[dfs(index: 当前枚举的数位从高到低)] --> B[state: 业务自定义约束状态 (如已使用的数字集合 mask / 上一位数字 lastDigit / 目标数字计数 count)] A --> C[isLimit: 受到高位数字上限约束的布尔标记] A --> D[isNum: 前面是否已经填入了真实有效数字 (前导零判定)]

1.`isLimit`（数位上界约束标记）：

含义：表示当前位填入的数字，是否受到原始数字 $N$ 对应位的最大上限约束；
举例：若原始数字 $N = 256$：
- 在百位上填了2，那么十位最多只能填到5（isLimit = true，上限为 $s[\text{index}]$）；
- 若在百位上填了1，那么十位可以从0自由填到9（isLimit = false，上限恒为 9）！
下一层传递：nextIsLimit = isLimit && (digit == up)。

2.`isNum`（有效数字与前导零标记）：

含义：表示当前位之前，是否已经填入了有效的正整数字；
前导零处理（Leading Zeros）：
- 若isNum = false：表示前面所有高位全部被跳过了（充当前导零）。当前位可以继续跳过（不填任何数字），递归进入dfs(index + 1, state, false, false)；或者当前位填入第一位真实有效数字digit \in [1, up]，此时将isNum激活为true！
重要作用：在要求“数字无重复”或“各位数字乘积”时，前导零0绝不能计入状态，必须依靠isNum精确剔除！

3. 终极记忆化规则：什么时候才能从`memo`数组中直接取缓存？

记忆化缓存黄金铁律：
当且仅当!isLimit && isNum（无上界约束且已经构成了合法数字）时，当前子树的搜索结果才能写入或读取memo[index][state]缓存！
因为当isLimit = true时，搜索空间被当前数字的上限严重截断，属于不完整的局部结果，严禁写入通用缓存！

三、工业级万能数位 DP 模板代码（LeetCode 233 数字 1 的个数）

import java.util.Arrays; public class DigitDpTemplate { private char[] s; private int[][] memo; public int countDigitOne(int n) { // 1. 将数字转化为字符串 this.s = String.valueOf(n).toCharArray(); int len = s.length; // 2. 初始化 memo 记忆化缓存数组 (index, count1) this.memo = new int[len][len + 1]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 代表未计算过 } // 3. 从最高位 (index=0) 开始搜索 // 初始时 count1 = 0, isLimit = true (最高位受 n 的最高位限制), isNum = false return dfs(0, 0, true, false); } /** * @param index 当前正在决策的数位索引 (从高位 0 到低位 len-1) * @param count 业务状态：历史上已经出现的数字 '1' 的累计个数 * @param isLimit 当前数位是否受到 n 对应位的上限约束 * @param isNum 之前是否已经填入了有效数字 (处理前导零) */ private int dfs(int index, int count, boolean isLimit, boolean isNum) { // 递归终止条件：已经枚举完所有数位 if (index == s.length) { return isNum ? count : 0; // 若构成了合法数字，返回统计的 1 的个数 } // 记忆化命中：只有在不受限制且已构成合法数字时，才能读取缓存 if (!isLimit && isNum && memo[index][count] != -1) { return memo[index][count]; } int res = 0; // 1. 选择一：当前位继续跳过不填任何数字 (仅当前面全无数字时合法) if (!isNum) { res += dfs(index + 1, count, false, false); } // 2. 选择二：在当前位填入具体数字 // 确定当前数位的下界与上界 int low = isNum ? 0 : 1; // 若前面没填数，当前位从 1 开始填；若前面已填数，从 0 开始填 int up = isLimit ? (s[index] - '0') : 9; // 若受限则最多填到 s[index]，否则可自由填到 9 for (int digit = low; digit <= up; digit++) { // 下一个状态的 isLimit: 原本受限且当前填了上限数字 boolean nextIsLimit = isLimit && (digit == up); // 累计数字 1 的个数 int nextCount = count + (digit == 1 ? 1 : 0); res += dfs(index + 1, nextCount, nextIsLimit, true); } // 记忆化写入：仅在无限制且有效数字时缓存结果 if (!isLimit && isNum) { memo[index][count] = res; } return res; } }

四、进阶实战：状态压缩 + 数位 DP（LeetCode 1012 至少有 1 位重复的数字）

题目转化：
计算区间 $[1, N]$ 内至少有 1 位重复数字的个数 $\iff$$N - \text{无任何重复数字的正整数个数}$！

在状态中引入状压二进制位掩码mask（mask的第 $d$ 位为 1 代表数字 $d$ 已经使用过）：

// 数位 DP + 状压剪枝核心片段 for (int digit = low; digit <= up; digit++) { // 检查数字 digit 是否已被使用过: (mask >> digit) & 1 == 1 if (((mask >> digit) & 1) == 0) { // 仅当未重复时才允许填入 res += dfs(index + 1, mask | (1 << digit), isLimit && (digit == up), true); } }

复杂度分析与总结

时间复杂度：状态总数为 $\text{len} \times \text{State} = 10 \times 10 = 100$ 种可能。单次状态仅枚举 $0 \sim 9$ 共 10 次循环，总计算量在微秒级（$< 1\text{ms}$）内完成！
心法口诀：
“从高到低逐位选，isLimit控上限，isNum跳前导，无界有效存缓存。”
掌握这套标准模版，后续面对任何数位统计、特定模式过滤与进制转换题型，你都能像套公式一样在 5 分钟内快速 AC。