数位DP

作者： beijian / 2021年5月23日

数位DP是一种用于解决与数字数位相关问题的动态规划技术，特别适合处理大范围内的数字统计问题。

一、核心概念

数位定义：将数字按位分解（如十进制的个、十、百位），每位取值范围为0到9（或其他进制对应范围）。
适用场景：
• 统计区间 [L, R] 内满足特定条件的数字个数（如不含数字4或连续62）
• 数据范围极大（如10¹⁸），无法暴力枚举。

二、算法思想

分治思想：将数字从高位到低位逐位处理，通过状态转移记录子问题解。
状态设计：
• pos：当前处理到的数位位置
• limit：当前位是否受上限约束（如数字123的十位若为2，个位最多取3）
• lead：是否有前导零（影响数字有效性判断）
• 其他自定义状态（如前一位数字pre、数字和sum等）

三、实现模板（C++）

typedef long long ll;
int a[20]; // 存储数字各位
ll dp[20][state]; // 状态数组，state根据问题定义

ll dfs(int pos, int state, bool lead, bool limit) {
    if (pos == -1) return 1; // 递归终止条件，根据问题调整返回值
    if (!limit && !lead && dp[pos][state] != -1) 
        return dp[pos][state]; // 记忆化

    int up = limit ? a[pos] : 9;
    ll res = 0;
    for (int i = 0; i <= up; ++i) {
        if (问题特定条件) continue; // 如i==4跳过
        res += dfs(pos-1, 新状态, lead && (i==0), limit && (i==up));
    }
    if (!limit && !lead) dp[pos][state] = res; // 记录非受限状态
    return res;
}

ll solve(ll x) {
    int pos = 0;
    while (x) { a[pos++] = x % 10; x /= 10; }
    memset(dp, -1, sizeof(dp));
    return dfs(pos-1, 初始状态, true, true);
}
// 调用：solve(R) - solve(L-1)

四、经典例题

不要62（HDU 2089）：
• 状态需记录前一位是否为6，当前位不能为2。
数字1的个数（LeetCode 233）：
• 统计每位出现1的次数，状态记录累计的1的数目。

五、优化技巧

二进制拆分：处理多重约束时合并状态。
状态压缩：用位运算记录数字使用情况（如state表示数字0-9是否出现过）。

六、复杂度分析

时间：O(log₁₀^N S)，S为状态数
空间：O(log₁₀^N S)

数位DP通过数位分解和状态复用，将指数级问题转化为多项式复杂度，是处理大数统计问题的利器。