数位DP：一个常见的动态规划问题

数位动态规划（Digit DP）是一个常见的动态规划技巧，通常用于解决一些与数字的每一位相关的问题。这类问题的核心思想是，基于数字的每一位进行状态转移和递推，并通过递归或迭代来实现状态的计算。

什么是数位DP？

数位DP（Digit DP）本质上是一种递归加动态规划的技术，旨在通过拆分一个数的每一位来进行状态转移，从而解决涉及数字限制（如范围内的数字，满足某些条件的数字等）的计数问题。其基本思想是将问题转换为对每一位数字进行枚举，递归地计算所有可能的解。

应用场景

数位DP通常用于以下类型的题目：

统计某个范围内符合条件的数字个数：例如，统计范围 [1, N] 中有多少数字满足某种特定的性质。
限制条件下的数字构造问题：例如，统计满足某个条件的数字的数量，或求解某个满足条件的最小/最大数字。

基本思路

数字的拆解：我们通常将数字从高位到低位拆解成每一位，这样就可以对每一位进行状态转移，逐步构建答案。
状态定义：状态通常由当前处理到的位置、是否还受到限制（即是否比原数小）以及其他需要记录的条件构成。
递推与记忆化：对于每一位数字，根据当前的状态，递推下一个状态。为了避免重复计算，通常会使用记忆化搜索来存储已经计算过的状态。
边界条件与初始化：递归的边界条件是处理完所有的数字位或者符合要求的数字已经被找到了。

DP状态设计

一般来说，数位DP的状态包括以下几个部分：

当前位置：表示当前处理到数字的哪一位。
是否严格小于当前的数：即是否已经超出了给定数字的范围。
其他特定条件：例如，某些特殊约束条件，像是否满足某些数字出现的次数、是否符合某些特定性质等。

递推关系

对于每一位数字，我们通常会枚举该位可以选择的数字，然后根据当前的状态转移到下一位。递推关系的设计依赖于当前数字是否受到“限制”，即是否还需要严格满足原数字的范围。如果不受限制，则可以选择任意数字。

常见优化技巧

1. 状态压缩

在某些问题中，状态空间可能非常大。为了解决这一问题，我们可以使用状态压缩技术，将多个状态合并成一个更紧凑的状态表示。常见的状态压缩方法包括按位存储状态、减少多余的状态变量等。

2. 剪枝与限制条件

有时候，递归过程中会遇到不需要继续计算的状态（如超出范围或不符合约束）。此时，可以使用剪枝技术，通过提前终止递归，减少不必要的计算。

3. 动态规划优化

如果数位DP中存在重复的计算任务，可以通过其他动态规划技巧进一步优化，例如迭代方式替代递归，或者使用滚动数组（Space Optimization）来减少内存使用。

数位DP的典型题目

例题 1：统计不含某个数字的数

问题描述：给定一个整数范围 [l, r] 和一个禁止的数字 d，统计范围内所有不包含数字 d 的数字的个数。

思路：我们将数位DP用于统计从 1 到 r 中不包含数字 d 的数字个数，再减去从 1 到 l-1 中不包含数字 d 的数字个数。

参考代码：

#include<bits/stdc++.h>
using namespace std;

int dp[20][2][2]; // dp[pos][is_less][has_forbidden]
int d; // 禁止的数字
string num; // 当前处理的数字

// dfs函数，pos表示当前位，is_less表示当前数字是否小于原始数，has_forbidden表示是否包含禁止数字
int dfs(int pos, int is_less, int has_forbidden) {
    if (pos == num.size()) {
        return has_forbidden == 0; // 如果没有包含禁止数字，则符合条件
    }

    if (dp[pos][is_less][has_forbidden] != -1) {
        return dp[pos][is_less][has_forbidden];
    }

    int limit = is_less ? 9 : num[pos] - '0';
    int res = 0;

    // 枚举当前位的数字
    for (int dig = 0; dig <= limit; ++dig) {
        if (dig == d) continue; // 如果当前数字等于禁止数字，跳过
        res += dfs(pos + 1, is_less || dig < limit, has_forbidden || (dig == d));
    }

    return dp[pos][is_less][has_forbidden] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int l, r;
    cin >> l >> r >> d;

    // 统计从1到r和1到l-1的符合条件的数字个数
    memset(dp, -1, sizeof(dp));
    num = to_string(r);
    int res_r = dfs(0, 0, 0); // 计算1到r的符合条件的数字个数

    memset(dp, -1, sizeof(dp));
    num = to_string(l - 1);
    int res_l = dfs(0, 0, 0); // 计算1到l-1的符合条件的数字个数

    cout << res_r - res_l << endl; // 输出最终结果
    return 0;
}

例题 2：统计数字包含某个数字的个数

问题描述：给定一个整数范围 [l, r]，统计范围内所有包含数字 d 的数字的个数。

思路：我们可以利用数位DP，通过递归计算符合条件的数字个数。这里可以通过修改上面的状态来统计包含 d 的数字。

参考代码：

#include<bits/stdc++.h>
using namespace std;

int dp[20][2][2]; // dp[pos][is_less][has_forbidden]
int d; // 目标数字
string num; // 当前处理的数字

// dfs函数，pos表示当前位，is_less表示当前数字是否小于原始数，has_forbidden表示是否包含目标数字d
int dfs(int pos, int is_less, int has_found) {
    if (pos == num.size()) {
        return has_found; // 如果找到了目标数字，则符合条件
    }

    if (dp[pos][is_less][has_found] != -1) {
        return dp[pos][is_less][has_found];
    }

    int limit = is_less ? 9 : num[pos] - '0';
    int res = 0;

    // 枚举当前位的数字
    for (int dig = 0; dig <= limit; ++dig) {
        res += dfs(pos + 1, is_less || dig < limit, has_found || (dig == d)); // 如果当前数字是d，则has_found变为1
    }

    return dp[pos][is_less][has_found] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int l, r;
    cin >> l >> r >> d;

    // 统计从1到r和1到l-1的包含d的数字个数
    memset(dp, -1, sizeof(dp));
    num = to_string(r);
    int res_r = dfs(0, 0, 0); // 计算1到r的符合条件的数字个数

    memset(dp, -1, sizeof(dp));
    num = to_string(l - 1);
    int res_l = dfs(0, 0, 0); // 计算1到l-1的符合条件的数字个数

    cout << res_r - res_l << endl; // 输出最终结果
    return 0;
}

例题 3：统计数字中数字和小于某个值的数

问题描述：给定一个整数范围 [l, r]，统计范围内所有数字的数字和小于 S 的数字个数。

思路：可以使用数位DP统计每一位数字的和，并在递归时加入限制，保证数字和小于 S。

参考代码：

#include<bits/stdc++.h>
using namespace std;

int dp[20][2][101]; // dp[pos][is_less][sum]
string num; // 当前处理的数字
int S; // 数字和限制

// dfs函数，pos表示当前位，is_less表示当前数字是否小于原始数，sum表示当前数字和
int dfs(int pos, int is_less, int sum) {
    if (sum >= S) return 0; // 如果数字和已经超过限制，直接返回0
    if (pos == num.size()) return 1; // 如果已经处理完所有位，返回1

    if (dp[pos][is_less][sum] != -1) {
        return dp[pos][is_less][sum];
    }

    int limit = is_less ? 9 : num[pos] - '0';
    int res = 0;

    // 枚举当前位的数字
    for (int dig = 0; dig <= limit; ++dig) {
        res += dfs(pos + 1, is_less || dig < limit, sum + dig); // 累加当前位数字的和
    }

    return dp[pos][is_less][sum] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int l, r;
    cin >> l >> r >> S;

    // 统计从1到r和1到l-1的符合条件的数字个数
    memset(dp, -1, sizeof(dp));
    num = to_string(r);
    int res_r = dfs(0, 0, 0); // 计算1到r的符合条件的数字个数

    memset(dp, -1, sizeof(dp));
    num = to_string(l - 1);
    int res_l = dfs(0, 0, 0); // 计算1到l-1的符合条件的数字个数

    cout << res_r - res_l << endl; // 输出最终结果
    return 0;
}

这些例题是数位DP的典型应用，核心思想是将数字从高位到低位拆解，并使用动态规划递归来计算符合条件的数字个数。我们可以通过仔细设计状态来优化算法，避免过多的重复计算。通过状态压缩、记忆化等技巧，可以大幅提升效率，解决复杂度较高的数位问题。

常见问题

如何优化状态空间：
- 在实际应用中，我们可以通过更精确的状态设计来减少状态空间的复杂度。比如，一些无关紧要的状态可以合并，减少不必要的状态转移。
如何处理多种条件：
- 当问题中涉及多个复杂的条件时，可以通过增加更多的状态来表示这些条件，比如考虑“某位数字是否为奇数”、“某位数字是否大于某个值”等条件。

数位动态规划（Digit DP）是一种常用于处理数字性质问题的动态规划技术，尤其适用于那些涉及数字的每一位的计数问题。其基本思想是通过拆解一个数字的每一位，并在每一位上进行状态转移与递推，从而求解符合特定条件的数字个数或构造满足约束的数字。数位DP通常利用递归与记忆化搜索来避免重复计算，提高效率。状态设计通常包括当前位置、是否小于原数、以及一些特定条件（如某些数字出现次数或和的限制）。通过递归地枚举每一位可能的数字，并根据当前状态转移到下一位，最终得到符合条件的解。数位DP广泛应用于范围统计问题，如统计范围内不包含某个数字的数字个数、包含特定数字的数字个数，或者满足某些数位和限制的数字个数等。通过优化状态空间和递推关系，数位DP能够高效解决一些复杂的数字性质问题，常用于竞赛和算法题中。