数位 DP 算法详解：从入门到实战，附带代码模板与避坑指南

在算法竞赛和实际工程中，我们经常会遇到与数字相关的统计问题，例如求某个区间内满足特定条件的数字个数。这类问题如果直接暴力枚举，往往会超时。而数位 DP 则是一种高效解决这类问题的利器，它利用数字的特性，将问题分解为子问题，通过记忆化搜索或递推的方式，大大降低时间复杂度。例如，我们需要统计[L, R]区间内包含数字“4”的数的个数，这个问题就可以通过数位 DP 解决。

数位 DP 的底层原理

数位 DP 的核心思想是分而治之和记忆化。我们将一个数字看作是由各位数字组成的，然后从高位到低位逐位考虑。在考虑每一位时，我们需要记录当前的状态，例如已经填了多少位数字，是否达到了上限等等。然后，根据当前的状态，我们可以确定当前位可以填哪些数字，并递归到下一位。由于很多状态会被重复访问，因此我们可以使用记忆化搜索或递推的方式，将已经计算过的状态保存下来，避免重复计算。

例如，我们需要统计区间 [L, R] 内各位数字之和能被 3 整除的数的个数。我们可以定义一个状态 dp[i][j][k]，其中 i 表示当前已经填了 i 位数字，j 表示当前的数字是否达到了上限，k 表示当前各位数字之和模 3 的余数。然后，我们可以根据当前的状态，确定当前位可以填哪些数字，并更新状态。

在实际应用中，数位 DP 经常与一些其他的算法和数据结构结合使用，例如二分查找、前缀和等。例如，我们可以使用二分查找来快速定位区间的边界，然后使用数位 DP 来统计区间内的数字个数。又例如，我们可以使用前缀和来预处理一些数据，然后使用数位 DP 来加速计算。

数位 DP 的代码模板与实战

下面给出一个常用的数位 DP 的代码模板，并结合一个实际的例子进行讲解。

代码模板（记忆化搜索）

#include <iostream>
#include <vector>

using namespace std;

int a[20]; // 用于存储数字的每一位
int dp[20][2]; // dp[i][j] 表示填了 i 位，j 表示是否达到上限的状态

// pos: 当前要填的位数，limit: 是否达到上限，sum: 当前的各位数字之和
int dfs(int pos, bool limit, int sum) {
    // 递归边界：已经填完了所有位数
    if (pos == -1) {
        return sum % 3 == 0; // 判断各位数字之和是否能被 3 整除
    }

    // 记忆化：如果已经计算过该状态，则直接返回结果
    if (!limit && dp[pos][sum] != -1) {
        return dp[pos][sum];
    }

    int up = limit ? a[pos] : 9; // 确定当前位可以填的最大数字
    int ans = 0;
    // 枚举当前位可以填的数字
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos - 1, limit && i == a[pos], (sum + i) % 3); // 递归到下一位
    }

    // 记忆化：保存计算结果
    if (!limit) {
        dp[pos][sum] = ans;
    }
    return ans;
}

// 计算区间 [l, r] 内各位数字之和能被 3 整除的数的个数
int solve(int x) {
    int pos = 0;
    // 将数字 x 拆分成每一位
    while (x) {
        a[pos++] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof(dp)); // 初始化 dp 数组
    return dfs(pos - 1, true, 0);
}

int main() {
    int l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << endl;
    return 0;
}

实战例子：统计区间 [L, R] 内不包含数字“4”的数的个数

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

using namespace std;

int a[20];
int dp[20][2];

int dfs(int pos, bool limit) {
    if (pos == -1) {
        return 1;
    }
    if (!limit && dp[pos][0] != -1) {
        return dp[pos][0];
    }
    int up = limit ? a[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++) {
        if (i == 4) continue; // 排除数字 4
        ans += dfs(pos - 1, limit && i == a[pos]);
    }
    if (!limit) {
        dp[pos][0] = ans;
    }
    return ans;
}

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

int main() {
    int l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << endl;
    return 0;
}

数位 DP 的避坑经验总结

1. 状态定义：状态定义是数位 DP 的关键。要根据问题的特点，合理地定义状态，确保能够覆盖所有可能的情况。
2. 边界条件：边界条件是数位 DP 的基础。要仔细考虑边界条件，确保递归能够正确结束。
3. 记忆化：记忆化是数位 DP 提高效率的关键。要将已经计算过的状态保存下来，避免重复计算。可以使用 memset 初始化 dp 数组，但要注意 -1 才能保证效果， 0 会导致部分测试用例失效。
4. 前导零：有些问题需要考虑前导零的情况。例如，统计区间 [L, R] 内不包含前导零的回文数的个数。可以使用一个变量来记录当前是否已经出现了非零数字，然后根据情况进行处理。
5. 数据范围：数位 DP 的数据范围通常比较大，需要使用 long long 类型来存储结果。 使用 int 类型可能导致溢出，从而得到错误的答案。此外，需要考虑题目中 L 和 R 的取值，避免出现类似 solve(l - 1) 导致的溢出问题。
6. 模板选择：数位 DP 可以使用记忆化搜索或递推的方式实现。对于一些复杂的问题，记忆化搜索可能更容易理解和实现。但对于一些简单的问题，递推可能效率更高。 例如对于并发量高的场景，使用递推可以有效避免栈溢出等问题，在诸如 Nginx 的配置中，也可以通过调整 worker 进程的数量来平衡并发和内存消耗。

熟练掌握数位 DP，可以帮助我们高效解决各种与数字相关的统计问题，在算法竞赛和实际工程中都能发挥重要的作用。同时，也需要注意避免上述的坑，才能写出正确高效的数位 DP 代码。