跳转至

数位动态规划 (Digit DP)

数位动态规划（简称数位 DP）专门用于解决形如：“在给定闭区间 \([L, R]\) 中，统计满足某种特定数位性质（如不含连续 1、各个数位之和为特定值、数位各不相同等）的整数个数”。其数值范围往往高达 \(10^{18}\) 乃至 \(10^{100}\)，暴力枚举必然 TLE，而数位 DP 能在 \(\mathcal{O}(\log_{10}(R) \times \text{状态数})\) 的极速时间内精确求解。

1. 核心数学思想：前缀差分拆解

区间 \([L, R]\) 内满足条件的数字数量，根据容斥与前缀差分原理，可以等价拆解为：

\[ \text{Count}([L, R]) = f(R) - f(L - 1) \]

其中 \(f(X)\) 表示在区间 \([0, X]\)（或 \([1, X]\)）中满足条件的数字个数。因此，问题彻底转化为：给定一个上限字符串 \(S\)（\(X\) 的十进制表示），统计不超过 \(S\) 的合法整数数量。

2. 工业级记忆化搜索通用框架

数位 DP 最清晰、最不易出错的编写范式是带前导零与上界标记的递归记忆化搜索（Memoized DFS）。

2.1 四大核心参数设计

int dfs(int pos, int state, bool is_limit, bool is_num);
  1. pos (当前数位)：从最高位（\(pos = 0\)）自左向右递归填数，直到到达最低位（\(pos = n\)）完成一个完整整数的构造；
  2. state (转移特征)：题目要求的具体数位状态（例如：当前数位和、上一位填的数字、已使用的数字位掩码集合等）；
  3. is_limit (上界约束标记)：
  4. 若 is_limit == true：当前位能填入的数字上限被严格卡死在 \(S[pos]\)。填入的数字只能在 \([0, S[pos] - '0']\) 中选择；
  5. 若 is_limit == false：前面某些位已经严格小于 \(S\) 的对应位，当前位拥有完全自由，可以不受限制地填入 \([0, 9]\)；
  6. is_num (前导零有效数字标记)：
  7. 若 is_num == false：前面所有高位都尚未填入有效数字（即全部视作前导零）。此时当前位可以选择跳过不填（继续保持前导零状态，迈向下一位），或者选填 \([1, up]\) 开始构造首位有效数字；
  8. 若 is_num == true：前面已经产生有效数字，当前位哪怕填 \(0\) 也代表合法的真实数位。

2.2 记忆化存储铁律 (Critical Rule of Memoization)

记忆化数组 memo[pos][state] 唯有在 !is_limit && is_num 时才允许查询和写入！

  • 为什么？
  • 当 is_limit == true 时，搜索空间受制于当前特定上限的前缀，其解是“残缺”的，绝不能当成通用的全集解存入记忆化；
  • 当 is_num == false 时，当前状态受前导零影响，亦非标准状态；
  • 只有当既不受上限束缚（可自由填 \(0 \sim 9\)），又已经是真实有效数字时，计算结果才具备真正的子问题通用性，可以被后续搜索直接复用！

3. 通用代码模板 (以 LeetCode 2719 统计数位和为例)

#include <string>
#include <vector>
#include <cstring>

class DigitDP {
    std::string s;
    int min_sum, max_sum;
    int memo[25][405]; // memo[pos][sum]

    // pos: 当前位; sum: 当前累计数位和; is_limit: 是否贴上界; is_num: 是否已填数字
    int dfs(int pos, int sum, bool is_limit, bool is_num) {
        if (sum > max_sum) return 0; // 剪枝
        if (pos == s.size()) {
            return is_num && sum >= min_sum;
        }

        // 仅在无约束且有效数字时读取记忆化
        if (!is_limit && is_num && memo[pos][sum] != -1) {
            return memo[pos][sum];
        }

        int res = 0;
        // 1. 若前面未填数字，当前位可继续跳过 (维持前导零)
        if (!is_num) {
            res = (res + dfs(pos + 1, sum, false, false)) % 1000000007;
        }

        // 2. 确定当前位填数字的上下界
        int low = is_num ? 0 : 1;
        int up = is_limit ? (s[pos] - '0') : 9;

        for (int d = low; d <= up; ++d) {
            res = (res + dfs(pos + 1, sum + d, is_limit && (d == up), true)) % 1000000007;
        }

        // 仅在无约束且有效数字时缓存记忆化
        if (!is_limit && is_num) {
            memo[pos][sum] = res;
        }
        return res;
    }

public:
    int count(std::string num, int min_s, int max_s) {
        s = num;
        min_sum = min_s;
        max_sum = max_s;
        std::memset(memo, -1, sizeof(memo));
        return dfs(0, 0, true, false);
    }
};
  • 时间复杂度：状态总数至多为 \(\text{位数} \times \text{数位和上限} \approx 25 \times 400 \approx 10^4\)，每个状态内循环至多 10 次，单次查询通常在数毫秒内极速完成。
  • 空间复杂度：\(\mathcal{O}(\text{位数} \times \text{状态数})\)。

4. LeetCode 经典真题精选与题解提示