数位DP：动态规划在数字处理中的高效应用

1. 数位DP：信奥赛选手必须掌握的动态规划利器

第一次接触数位DP是在备战CSP-S复赛时，当时遇到一道关于数字统计的题目让我束手无策。传统暴力解法在数据范围达到1e18时完全失效，而数位DP却能在毫秒级完成计算。这种神奇的时间复杂度反差让我彻底迷上了这个算法。

数位DP（Digit DP）是动态规划在数字处理问题中的特殊应用，它通过逐位处理数字的方式，将原本指数级的问题转化为多项式时间复杂度。在信奥赛C++提高组竞赛中，约30%的DP类题目都会涉及数位处理技巧，特别是CSP-S第二题常考的计数问题。

关键认知：数位DP不是一种独立算法，而是动态规划思想与数位分解技术的结合体。掌握它需要同时理解DP的状态设计和数字的位运算特性。

2. 数位DP核心原理拆解

2.1 基本问题模型

典型数位DP问题通常具有以下特征：

• 统计满足特定条件的数字个数
• 数字范围极大（1e18级别）
• 条件与数字的组成相关（如不含某些数字、数位和特定等）

以经典例题为例：统计[L,R]范围内不含4且不含62的数字个数。暴力枚举在R=1e18时显然不可行，而数位DP可以将时间复杂度降至O(log10(R)*K)，其中K是状态维度。

2.2 状态设计三要素

1. 数位位置pos：当前处理到数字的第几位（从高位到低位）
2. 边界限制limit：前几位是否已经达到n的对应位（决定当前位取值范围）
3. 状态标记state：根据题目条件定义（如前一位是否为6、数位和等）

cpp复制int dp[pos][limit][state]; // 典型状态表示

2.3 记忆化搜索实现框架

数位DP通常采用记忆化搜索（DFS+Memoization）实现，比递推更易理解：

cpp复制int dfs(int pos, int limit, int state) {
    if(pos == -1) return check(state); // 数字构造完成
    if(!limit && dp[pos][state] != -1) 
        return dp[pos][state]; // 记忆化检索
    
    int res = 0;
    int upper = lim