目录

一、数位DP的核心概念

二、数位DP的三大核心要素

三、数位DP解题四步法

1. 数位转换

2. 状态设计

3. 记忆化缓存

4. DFS递归处理

四、经典案例：禁止62和4的数字统计

问题描述

输入示例

五、Java实现代码

六、代码解析

1. 状态转移逻辑

2. 复杂度分析

七、关键优化技巧

1. 状态压缩

2. 预处理加速

3. 双端处理

八、常见问题解决

1. 前导零处理不当

2. 状态设计冗余

3. 大数处理溢出

九、LeetCode实战训练

十、总结

---

一、数位DP的核心概念

        数位DP（Digit Dynamic Programming） 是用于解决数字各位相关计数问题的高效算法，特别适用于处理区间内满足特定条件的数字个数统计。典型应用场景包括：

• 数字禁忌规则：排除含特定数字（如4）或模式（如62）

• 数字属性统计：计算数字各位和、回文数判断等

• 数位约束问题：满足各位递增/递减等条件

---

二、数位DP的三大核心要素

要素	作用描述	示例
数位分解	将数字转为逐位处理的数组	123 → [1,2,3]
状态设计	记录处理过程中的关键信息	前导零标记、前位数值
记忆化搜索	避免重复计算的优化手段	缓存相同状态结果

---

三、数位DP解题四步法

1. 数位转换

将数字转换为字符数组或整数数组：

int[] num = Integer.toString(n).chars().map(c -> c-'0').toArray();

2. 状态设计

定义状态维度（常用三维）：

• pos：当前处理的数位位置

• limit：是否受原始数字限制

• prev：前一位数字值

• leadingZero：前导零标记（可选）

3. 记忆化缓存

使用dp[pos][prev][limit]存储已计算状态

4. DFS递归处理

按位枚举可能值，根据约束条件剪枝

---

四、经典案例：禁止62和4的数字统计

问题描述

求区间[L, R]内满足以下条件的数字个数：

1. 不包含数字4

2. 不包含连续62（如1623允许，但6231禁止）

输入示例

输入：L=1，R=100  
输出：80  
解释：排除4、62及含4的数字

---

五、Java实现代码

public class DigitDP {
    private int[] num;
    private Integer[][][] dp;

    public int countValidNumbers(int n) {
        num = convert(n);
        dp = new Integer[num.length][10][2];
        return dfs(0, 0, true, true);
    }

    // pos: 当前处理位索引
    // prev: 前一位数字
    // limit: 是否受原始数字限制
    // leadingZero: 是否前导零阶段
    private int dfs(int pos, int prev, boolean limit, boolean leadingZero) {
        if (pos == num.length) return leadingZero ? 0 : 1;
        
        int upper = limit ? num[pos] : 9;
        int res = 0;
        
        // 记忆化检索
        if (!leadingZero && dp[pos][prev][limit ? 1 : 0] != null) 
            return dp[pos][prev][limit ? 1 : 0];
        
        for (int d = 0; d <= upper; d++) {
            // 跳过非法数字
            if (d == 4) continue;
            if (!leadingZero && prev == 6 && d == 2) continue;
            
            boolean nextLimit = limit && (d == upper);
            boolean nextLeadingZero = leadingZero && (d == 0);
            int nextPrev = nextLeadingZero ? 0 : d;
            
            res += dfs(pos+1, nextPrev, nextLimit, nextLeadingZero);
        }
        
        // 记忆化存储（前导零状态不缓存）
        if (!leadingZero) 
            dp[pos][prev][limit ? 1 : 0] = res;
        return res;
    }

    private int[] convert(int n) {
        char[] chars = Integer.toString(n).toCharArray();
        int[] arr = new int[chars.length];
        for (int i = 0; i < chars.length; i++) 
            arr[i] = chars[i] - '0';
        return arr;
    }

    public static void main(String[] args) {
        DigitDP solver = new DigitDP();
        System.out.println(solver.countValidNumbers(100)); // 输出80
    }
}

---

六、代码解析

1. 状态转移逻辑

• 数字筛选：跳过4和形成62的情况

• 前导零处理：允许前导零但不计入结果

• 限制传递：当选择数字等于上限值时，下一位继续受限

---

七、关键优化技巧

1. 状态压缩

• 合并前导零标记到状态中

• 使用位运算代替布尔标记

2. 预处理加速

• 预先计算不同位数的合法数字数量

3. 双端处理

• 分别计算[1,R]和[1,L-1]的结果做差

---

八、常见问题解决

1. 前导零处理不当

• 明确前导零是否算有效数字

• 在最终结果中扣除纯零情况

2. 状态设计冗余

• 分析哪些维度可以合并或省略

• 例如：当不需要连续信息时，可省略prev维度

3. 大数处理溢出

• 使用字符串直接处理超过long范围的数字

• 采用逆序处理降低复杂度

---

九、LeetCode实战训练

1. 基础练习

   • 数字1的个数

   • 统计各位数字都不同的数字个数
   • 不含连续1的非负整数

2. 进阶挑战

   •  最大为N的数字组合

   • 至少有1位重复的数字
   • 范围内的数字计数

---

十、总结

数位DP的核心在于将数字视为位序列处理，通过以下步骤高效解决问题：

1. 数位分解 → 2. 状态设计 → 3. 记忆化搜索 → 4. 结果合成