📖 第 6.5 章：数位 DP（Digit DP）

⏱ 预计阅读时间：50 分钟 | 难度：🟡 中等（USACO Gold 高频考点）

前置条件

• DP 入门（第 6.1 章）
• 经典 DP 问题（第 6.2 章）

🎯 学习目标

学完本章后，你将能够：

1. 理解数位 DP 的核心框架：按位从高到低填数
2. 掌握「tight（是否贴上界）」标志的作用
3. 处理「前导零」问题
4. 解决「区间 [L, R] 内满足某数字性质的数的个数」类问题

6.5.1 问题引入

一类常见问题

统计 1 到 N 中，满足某种「数字属性」的整数个数。

示例：

• [1, N] 中各位数字之和等于 S 的数的个数
• [1, N] 中不含数字 4 的数的个数
• [1, N] 中各位数字单调不降的数的个数

为什么不能暴力？ N 可能高达 10^18，逐一枚举完全不可能。

核心思路： 像「填数字」一样，从最高位到最低位逐位枚举，用 DP 记录状态，避免重复计算。

6.5.2 数位 DP 的框架

核心状态

关键逻辑

如果 tight == true：
    当前位只能填 0 ~ digit[pos]（digit[pos] 是 N 的第 pos 位）
    填 digit[pos] 时，下一位仍然 tight
    填 < digit[pos] 时，下一位不再 tight（自由了！）

如果 tight == false：
    当前位可以填 0~9（自由枚举）
    下一位也不 tight

6.5.3 完整例题一：各位数字之和

问题： 统计 1 到 N 中，各位数字之和恰好等于 S 的正整数个数。

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

string num_str;  // N 的字符串表示
int target_sum;  // 目标数字和 S

// dp[pos][sum_so_far][tight][started]
// 记忆化，避免重复计算相同状态
map<tuple<int,int,bool,bool>, long long> memo;

// pos: 当前位（从 0 开始，0 是最高位）
// sum: 已填数字的和
// tight: 是否贴上界
// started: 是否已经开始（用于处理前导零）
long long solve(int pos, int sum, bool tight, bool started) {
    if (sum > target_sum) return 0;  // 剪枝：和已超出
    
    if (pos == (int)num_str.size()) {
        // 填完所有位
        return (started && sum == target_sum) ? 1 : 0;
    }
    
    auto key = make_tuple(pos, sum, tight, started);
    if (memo.count(key)) return memo[key];
    
    int limit = tight ? (num_str[pos] - '0') : 9;
    long long result = 0;
    
    for (int d = 0; d <= limit; d++) {
        bool new_tight = tight && (d == limit);
        bool new_started = started || (d != 0);
        int new_sum = (new_started ? sum + d : 0);  // 前导零不计入和
        result += solve(pos + 1, new_sum, new_tight, new_started);
    }
    
    return memo[key] = result;
}

long long count_up_to(long long N, int S) {
    num_str = to_string(N);
    target_sum = S;
    memo.clear();
    return solve(0, 0, true, false);
}

int main() {
    long long L, R; int S;
    cin >> L >> R >> S;
    // 区间 [L, R] = f(R) - f(L-1)
    cout << count_up_to(R, S) - count_up_to(L - 1, S) << "\n";
    return 0;
}

追踪（N=20, S=2）：

填第 0 位（最高位，limit=2）：
  d=0（未 started）：进入 (1, 0, false, false)
    填第 1 位（1-9）：
      d=2：(ended, sum=2, tight=false) → 1（即数字 02 = 2）
      其余不满足 sum=2
  d=1（started=true）：进入 (1, 1, false, true)
    填第 1 位（0-9）：
      d=1：(ended, sum=2) → 1（即 11）
  d=2（tight）：进入 (1, 2, false, true)
    填第 1 位（0-9）：
      d=0：(ended, sum=2) → 1（即 20）
      其他 sum > 2 → 0

合计：2（数字 2 和 11 和 20）

6.5.4 数位 DP 通用模板（更简洁版）

竞赛中通常用数组代替 map 做记忆化：

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

int digits[20];         // N 的各位数字（从高位到低位）
int n_digits;           // 总位数
ll dp[20][200][2][2];   // dp[pos][sum][tight][started]
                        // 维度根据问题调整
bool computed[20][200][2][2];
int S;  // 目标数字和

ll solve(int pos, int sum, bool tight, bool started) {
    if (sum > S) return 0;
    if (pos == n_digits) return (started && sum == S) ? 1 : 0;
    
    ll& ret = dp[pos][sum][tight][started];
    if (computed[pos][sum][tight][started]) return ret;
    computed[pos][sum][tight][started] = true;
    
    int lim = tight ? digits[pos] : 9;
    ret = 0;
    for (int d = 0; d <= lim; d++) {
        ret += solve(pos + 1,
                     (started || d > 0) ? sum + d : 0,
                     tight && (d == lim),
                     started || (d > 0));
    }
    return ret;
}

ll count_up_to(ll N) {
    n_digits = 0;
    while (N > 0) { digits[n_digits++] = N % 10; N /= 10; }
    reverse(digits, digits + n_digits);
    memset(computed, 0, sizeof(computed));
    return solve(0, 0, true, false);
}

int main() {
    ll L, R; cin >> L >> R >> S;
    cout << count_up_to(R) - count_up_to(L - 1) << "\n";
}

6.5.5 例题二：不含连续相同数字

问题： 统计 [L, R] 中，没有两个相邻数字相同的整数个数。
（例：123、145 满足，122、344 不满足）

额外状态： last_digit（上一位填的数字）

ll dp2[20][11][2][2];  // [pos][last_digit][tight][started]
// last_digit: 0~9 表示上一位数字，10 表示"还没开始"

ll solve2(int pos, int last, bool tight, bool started) {
    if (pos == n_digits) return started ? 1 : 0;
    
    ll& ret = dp2[pos][last][tight][started];
    if (computed[pos][last][tight][started]) return ret;
    computed[pos][last][tight][started] = true;
    
    int lim = tight ? digits[pos] : 9;
    ret = 0;
    for (int d = 0; d <= lim; d++) {
        // 已 started 时，禁止 d == last（相邻相同）
        if (started && d == last) continue;
        
        ret += solve2(pos + 1,
                      (started || d > 0) ? d : 10,   // 前导零时 last 不更新
                      tight && (d == lim),
                      started || (d > 0));
    }
    return ret;
}

6.5.6 例题三：各位数字单调不降

问题： 统计 [1, N] 中，各位数字从左到右单调不降的整数个数。
（例：1359、2233 满足，132、231 不满足）

额外状态： min_digit（当前允许填的最小数字）

ll dp3[20][10][2][2];  // [pos][min_allowed][tight][started]

ll solve3(int pos, int min_d, bool tight, bool started) {
    if (pos == n_digits) return started ? 1 : 0;
    
    ll& ret = dp3[pos][min_d][tight][started];
    // ... 记忆化判断 ...
    
    int lim = tight ? digits[pos] : 9;
    ret = 0;
    for (int d = (started ? min_d : 0); d <= lim; d++) {
        ret += solve3(pos + 1,
                      d,           // 下一位不能小于 d
                      tight && (d == lim),
                      true);
    }
    return ret;
}

6.5.7 区间查询：f(R) - f(L-1)

几乎所有数位 DP 都满足区间可减性：

$$\text{count}[L, R] = \text{count}[1, R] - \text{count}[1, L-1]$$

所以 count_up_to(N) 函数是核心，用它两次就能回答区间查询。

注意： 当 L = 0 时，L - 1 = -1 需要特殊处理（count_up_to(-1) = 0）。

6.5.8 常见数位 DP 问题类型

⚠️ 常见错误

💪 练习题

🟢 题目 1：不含数字 4

统计 [1, N] 中不含数字 4 的整数个数（N ≤ 10^15）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int digits[20], n_digits;
ll dp[20][2][2];
bool vis[20][2][2];

ll solve(int pos, bool tight, bool started) {
    if (pos == n_digits) return started ? 1 : 0;
    ll& ret = dp[pos][tight][started];
    if (vis[pos][tight][started]) return ret;
    vis[pos][tight][started] = true;
    int lim = tight ? digits[pos] : 9;
    ret = 0;
    for (int d = 0; d <= lim; d++) {
        if (d == 4) continue;  // 不含4
        ret += solve(pos + 1, tight && (d == lim), started || (d > 0));
    }
    return ret;
}

ll count_up_to(ll N) {
    if (N <= 0) return 0;
    n_digits = 0;
    ll tmp = N;
    while (tmp) { digits[n_digits++] = tmp % 10; tmp /= 10; }
    reverse(digits, digits + n_digits);
    memset(vis, 0, sizeof(vis));
    return solve(0, true, false);
}

int main() {
    ll L, R; cin >> L >> R;
    cout << count_up_to(R) - count_up_to(L - 1) << "\n";
}

🟡 题目 2：各位数字和为 S

统计 [L, R] 中各位数字之和恰好为 S 的整数个数（L, R ≤ 10^18，S ≤ 162）。

🔴 题目 3：各位数字单调不降 + 数字和 ≤ K

统计 [1, N] 中，各位数字单调不降且数字之和不超过 K 的整数个数（N ≤ 10^15，K ≤ 100）。

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

int n_digits, K;
int digits[20];
ll dp[20][10][101][2][2];
bool vis[20][10][101][2][2];

ll solve(int pos, int last, int sum, bool tight, bool started) {
    if (sum > K) return 0;
    if (pos == n_digits) return started ? 1 : 0;
    
    ll& ret = dp[pos][last][sum][tight][started];
    if (vis[pos][last][sum][tight][started]) return ret;
    vis[pos][last][sum][tight][started] = true;
    
    int lim = tight ? digits[pos] : 9;
    ret = 0;
    for (int d = (started ? last : 0); d <= lim; d++) {
        ret += solve(pos + 1, d, (started || d > 0) ? sum + d : 0,
                     tight && (d == lim), started || (d > 0));
    }
    return ret;
}

ll count_up_to(ll N) {
    if (N <= 0) return 0;
    n_digits = 0; ll tmp = N;
    while (tmp) { digits[n_digits++] = tmp % 10; tmp /= 10; }
    reverse(digits, digits + n_digits);
    memset(vis, 0, sizeof(vis));
    return solve(0, 0, 0, true, false);
}

int main() {
    ll L, R; cin >> L >> R >> K;
    cout << count_up_to(R) - count_up_to(L - 1) << "\n";
}

💡 章节联系： 数位 DP 是 USACO Gold 每年必出的题型之一。它将「计数问题」转化为「逐位填数的决策 DP」，是 DP 思想的精华体现。掌握后可进一步学习「数位 + 组合数学」的双重计数技巧。