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

动态规划进阶数位 DPDigit DP与记忆化搜索模板数字计数与无重复数字排列在算法竞赛与大厂算法高频 Hard 题中有一类题目形式极其统一、但若使用暴力循环统计必然会在 $N 10^9 \sim 10^{18}$ 时直接超时TLE的经典专题LeetCode 233数字 1 的个数Number of Digit OneLeetCode 902最大为 N 的数字组合LeetCode 1012至少有 1 位重复的数字Numbers With Repeated DigitsLeetCode 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那么十位最多只能填到5isLimit true上限为 $s[\text{index}]$若在百位上填了1那么十位可以从0自由填到9isLimit 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. 从最高位 (index0) 开始搜索 // 初始时 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; } }四、进阶实战状态压缩 数位 DPLeetCode 1012 至少有 1 位重复的数字题目转化计算区间 $[1, N]$ 内至少有 1 位重复数字的个数 $\iff$$N - \text{无任何重复数字的正整数个数}$在状态中引入状压二进制位掩码maskmask的第 $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。