数位动态规划：高效计数与状态管理的深度解析

核心逻辑与数学原理

数位动态规划（Digit DP）的核心本质是将数值大小的宏观比较，降维映射为数字在特定进制下从高位到低位的“字符串式”拓扑状态转移。

数位 DP 专用于解决“在区间 $[L, R]$ 中，满足某种特定数位特征（如：不含 49、相邻数位之差 $ ge 2$、各数位之和为质数等）的整数个数”这一类计数问题。它的核心思想在于利用前缀和转化、记忆化搜索以及高位对低位的上限约束控制。

1. 空间的几何化拆分：前缀和差分

直接在区间 $[L, R]$ 中求满足条件的数往往需要面对复杂的双边界制约。数位 DP 严格遵守前缀和差分原理，将任意区间查询转换为以 0 为起点的独立单边查询：

$$ \text{Ans}(L, R) = \text{Ans}(0, R) - \text{Ans}(0, L - 1) $$

这使得我们只需要专注于解决“求 $[0, N]$ 中有多少个数满足条件”这一核心命题。

2. 数值上限的拓扑解耦：limit 标记原理

假设 $N = 3125$。当我们从最高位（千位）开始向低位填数字时：

• 如果千位填了 1 或 2，那么百位上可以任意填写 0 ~ 9 之间的任何数字，都不会超过 $N$ 的限制。此时，低位的填写完全失去了高位的上限约束，其局部状态是全同构的。
• 如果千位填了 3，那么百位上至多只能填写 1。如果百位填了 0，十位就可以放开随便填 0 ~ 9；如果百位填了 1，十位至多只能填 2。

这种高位数字的选择对低位可选范围造成的动态制约，在数位 DP 中被称为 limit 限制：

• 当 limit = true 时，当前位能填写的数字上限被严格卡在 $N$ 的当前数位上；
• 当 limit = false 时，当前位能填写的数字上限自动解放为该进制的最大数字（十进制下为 9）。

状态设计与记忆化搜索网络

数位 DP 最标准、最不容易出错的考场实现方案是基于 DFS 的记忆化搜索（Memoized Search）。

1. DFS 状态空间的标准控制骨架

标准的数位 DP 搜索函数通常包含以下核心控制参数： int dfs(int pos, int state, bool lead, bool limit)

• pos：当前决策的数位。通常从最高位开始，递减到 0（最低位）时触底反弹返回 1。
• state：记录前驱数位对当前数位造成的约束状态（如：前一数位填了什么数字、之前所有数字的和等）。
• lead：前导零（Leading Zero）标记。如果 lead = true，代表当前位之前全都是 0（如数字 0025）。这在某些题目中极为关键，因为前导零不属于数字的有效组成部分。例如，若题目要求“相邻两位不能相同”，如果 lead = true，我们在当前位填 0 是合法的（即数字 0 变为有效数字开始），而不能误判定它与上一位的“前导零”相同。
• limit：上限最高位锁，控制当前位数字枚举的物理上界。

2. 状态记忆化的核心条件

数位 DP 的记忆化数组 f[pos][state] 能够被复用的先决条件是：当前搜索分支必须处于 limit = false 且 lead = false 的状态。

物理原因：如果 limit = true，说明当前搜索出来的总数受到了 $N$ 的局部限制，它不是全集，不能写进全局记忆化数组中。只有当上限被完全释放、前导零完全脱离时，低位搜索出来的解才具备普适性，才能被固化进 f 数组。

C++ 标准源码（NOIP/提高组全能模板）

以下源码解决数位 DP 经典入门问题：“求区间 $[L, R]$ 内不含数字 4 且不含连续数字 62 的数字个数”（洛谷 P2602 / 经典迎风流数位 DP 模型），严格兼容 Linux g++ -O2 环境。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int digits[20]; // 拆解存储数字 N 的各个数位
int f[20][10];  // f[pos][pre_digit] 记忆化状态网格

// pos: 当前位; pre: 上一位填的数字; lead: 是否有前导零; limit: 是否有最高位限制
int dfs(int pos, int pre, bool lead, bool limit) {
    // 终局条件：所有数位决策完毕，成功组合出一个合法的合法数，返回 1
    if (pos < 0) return 1;

    // 记忆化触发：只有在无任何限制、且无前导零的“自由状态”下，才能引用旧缓存
    if (!limit && !lead && f[pos][pre] != -1) {
        return f[pos][pre];
    }

    // 动态计算当前位的数字枚举上界
    int up = limit ? digits[pos] : 9;
    int res = 0;

    for (int i = 0; i <= up; ++i) {
        // 剪枝拦截：不能包含 4
        if (i == 4) continue;
        // 剪枝拦截：不能包含连续的 62
        if (pre == 6 && i == 2) continue;

        // 递归传递控制：
        // 1. 新的前导零状态：当前是前导零且当前位填了 0，则下一位依然是前导零
        // 2. 新的最高位限制：当前有限制且当前位填到了理论上限数字，下一位才会有最高位限制
        res += dfs(pos - 1, i, lead && (i == 0), limit && (i == up));
    }

    // 固化状态缓存：只有自由状态才能记录
    if (!limit && !lead) {
        f[pos][pre] = res;
    }

    return res;
}

// 求解 [0, n] 内合法的数字总量
int solve(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1; // 0 本身是一个合法的数字（不含4，不含62）

    int len = 0;
    // 将十进制数字从低位到高位拆解打散入数组
    while (n > 0) {
        digits[len++] = n % 10;
        n /= 10;
    }

    // 启动递归：从最高有效位 (len - 1) 开始，上一位赋予安全哨兵值 0，初始处于最高位限制与前导零中
    return dfs(len - 1, 0, true, true);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(f, -1, sizeof(f)); // 全局状态网格只需初始化一次

    int l, r;
    while (cin >> l >> r && (l || r)) {
        // 利用前缀和差分无损斩获区间答案
        cout << solve(r) - solve(l - 1) << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 记忆化数组误在 solve 函数内反复初始化

• 现象：很多选手习惯在每次调用 solve(n) 时，在函数内部执行 memset(f, -1, sizeof(f))。这在区间单次查询时没有问题，但在多组数据或大区间查询下，数位 DP 的核心优势（跨数值的全同构状态复用）会被彻底抹杀。每次清空意味着对每一组数据都要重新跑一遍满状态 DFS，直接导致常数暴增引发 TLE（运行超时）。
• 规避手段：由于数位 DP 剥离了 limit 和 lead 后的局部状态完全取决于当前位置 pos 和数位统计状态 state，与具体的 $N$ 毫无关系。因此，记忆化数组 f 应当在 main 函数开头初始化一次，终身复用。

2. 忽略 solve(L - 1) 当 $L=0$ 时的边界下溢出

• 现象：当题目中给定的区间起点 $L = 0$ 时，程序会去执行 solve(-1)。如果在 solve 函数开头没有对负数进行安全拦截，会导致数组越界或逻辑坍塌。
• 规避手段：在 solve 入口处严格加入 if (n < 0) return 0; 的边界哨兵。

经典 NOIP/洛谷 真题

1. 洛谷 P2602 [ZJOI2010] 数字计数

• 题意描述：给定两个正整数 $a$ 和 $b$，求在 $[a, b]$ 中的所有整数中，每个数码（$0 \sim 9$）各出现了多少次。$a, b \le 10^{12}$。
• 问题本质与解题思路：带有独立计数器的数位 DP。
• 核心思路：由于要统计具体每个数码的出现次数，我们可以对 $0 \sim 9$ 这 10 个数字分别跑一次数位 DP，或者在 DFS 状态中多加一维 count 记录目标数字当前已经出现的次数。在本题中，前导零判定（lead）极为关键：在统计数字 0 的出现次数时，如果是前导零（如 00023 中的前三个零），绝不能计入答案。只有当 lead = false 之后的零才是数字中合法的有效组成部分。

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

• 题意描述：求区间 $[L, R]$ 内所有整数的各位数字之和的总和。答案对 $10^9+7$ 取模。$L, R \le 10^{18}$。
• 问题本质与解题思路：数位求和类权值累加数位 DP。
• 核心思路：这题要求的不再是“满足条件的数的个数”，而是“所有数的指标累加”。
• 状态设计：dfs(pos, sum, lead, limit)。其中 sum 记录高位已经选定的数字之和。
• 返回值修正：当 pos < 0 触底时，不再返回 1，而是直接返回当前路径积累下来的 sum。通过这种方式，DFS 能够在回溯时自然把所有路径的数字和进行加权求和。由于数据规模达 $10^{18}$，中间结果和记忆化数组必须全部采用 long long 维护，并在每次加法操作后及时取模。