数位DP算法详解：从原理到竞赛实战

1. 数位DP算法概述

数位动态规划（Digit Dynamic Programming）是处理数字区间统计问题的利器。我第一次接触这个算法是在准备蓝桥杯竞赛时，当时遇到一道统计数字出现次数的题目，暴力解法直接超时，这才意识到数位DP的重要性。

1.1 算法特点与应用场景

数位DP最擅长处理两类典型问题：

1. 统计区间[L,R]内满足特定数位条件的数字个数
2. 计算区间内数字的某种数位特征总和（如数位和、特定数位出现次数等）

这类问题的共同特点是数据范围极大（通常达到1e18级别），但约束条件仅与数字的数位组成相关。例如：

• 统计1e18以内所有不含"4"的数字个数
• 计算1e12到1e18之间数位和为素数的数字数量
• 找出所有相邻数位差至少为2的"windy数"

提示：当看到题目要求统计"在[a,b]区间内满足...的数字"且a,b范围极大时，首先考虑数位DP解法

1.2 算法优势分析

与传统暴力枚举相比，数位DP将时间复杂度从O(R-L+1)优化到O(logR × S × 10)，其中：

• logR：数字的位数（1e18对应约20位）
• S：状态数（通常为常数级别）
• 10：每位数字0-9的枚举

这种优化使得处理1e18规模的区间成为可能，是算法竞赛中处理大数统计问题的标准解法。

2. 数位DP核心原理与实现框架

2.1 算法核心思想

数位DP的本质是"数位分解+记忆化搜索"，其核心步骤包括：

1. 数位拆分：将数字转换为数位数组（如123→[3,2,1]）
2. 记忆化DFS：从高位到低位枚举，记录三种关键状态：
   • pos：当前处理到的数位位置
   • limit：是否受到原数对应位限制
   • 自定义状态：根据题目需求而定
3. 前缀和转换：利用solve(R)-solve(L-1)计算区间结果
4. 记忆化存储：缓存无限制状态的中间结果

2.2 通用模板实现

以下是C++实现的通用数位DP框架：

cpp复制#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int a[20];       // 数位数组（低位在前）
LL dp[20][...];  // 记忆化数组，维度根据题目调整

// pos:当前位, limit:是否受限, ...:其他状态
LL dfs(int pos, bool limit, ...) {
    // 递归终止条件
    if(pos == 0) return ...; 
    
    // 记忆化查询（仅无限制状态）
    if(!limit && dp[pos][...] != -1) 
        return dp[pos][...];
    
    int up = limit ? a[pos] : 9;
    LL res = 0;
    for(int i=0; i<=up; ++i) {
        // 根据题目要求更新状态
        res += dfs(pos-1, limit && (i==up), ...);
    }
    
    // 记忆化存储（仅无限制状态）
    if(!limit) dp[pos][...] = res;
    return res;
}

LL solve(LL x) {
    int len = 0;
    while(x) {
        a[++len] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof dp);
    return dfs(len, tru