数位 DP 从入门到精通：模板与经典例题详解

数位 DP 是处理"范围内满足某条件的数的个数"这类问题的标准方法。

一、什么是数位 DP？
按数位（个位、十位、百位...）逐位进行 DP，通常解决这类问题：

• 求 [L, R] 内满足某种性质的数的个数


• 求 [L, R] 内不含某些数字的数的个数

int dp[20][state]; // pos: 当前位, state: 状态
int dfs(int pos, int state, bool limit, bool lead) {
    if (pos == 0) return check(state);
    if (!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
    int up = limit ? num[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos-1, next_state(state, i), limit && i==up, lead && i==0);
    }
    if (!limit && !lead) dp[pos][state] = ans;
    return ans;
}

• pos：当前处理的位数（从高位到低位）


• state：当前状态（根据题目设计）


• limit：是否卡上限（前面对应位置都等于上限数字）


• lead：是否有前导零

• 最简单的：是否需要记录已经出现过哪些数字


• 模运算：记录当前数 mod 某个值的余数


• 差分：用前缀和思想，solve(R) - solve(L-1)

1. 洛谷 P2657 windy 数（相邻数字差 >= 2）


2. 洛谷 P2602 数字计数（统计每个数字出现次数）


3. 洛谷 P4124 手机号码（包含特定数字组合）


4. 洛谷 P4999 烦人的数学作业

• 记忆化只在不卡上限、无前导零时记录


• 状态压缩存储"已出现过哪些数字"


• 同时处理多个约束