数位动态规划（Digit DP）深度解析：从原理到实战（C++实现）

数位动态规划是解决数字位相关计数问题的强大工具，特别适用于统计满足特定条件的数字数量。本文将系统讲解数位DP的核心思想、状态设计、模板实现及优化技巧，包含20+经典问题解析与C++实现。

数位DP本质：在数字的每一位上进行状态转移，同时处理数字本身的限制条件

一、数位DP基础概念

1.1 什么是数位DP

数位DP是一种针对数字位数设计的动态规划方法，用于解决以下类型问题：

• 统计区间[L, R]内满足特定条件的数字个数
• 求满足条件的第K小数字
• 数字各位属性统计（和、乘积、特定模式等）

1.2 数位DP的三大特征

1. 数字范围大：通常L,R在1e18以上
2. 条件与位数相关：如包含特定数字、各位和限制等
3. 可分解性：问题可分解到每位独立处理

1.3 数位DP的核心思想

• 数位分解：将数字分解为单个数位（digit-by-digit）
• 状态压缩：记录关键状态（前导零、是否受限、历史信息）
• 记忆化搜索：避免重复计算相同状态

二、数位DP通用模板

2.1 基本框架

#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

ll dp[20][state_size]; // 位数 x 状态大小
vector<int> digits;    // 存储每位数字

// 将数字分解为各位数字
vector<int> get_digits(ll n) {
    vector<int> d;
    while (n) {
        d.push_back(n % 10);
        n /= 10;
    }
    reverse(d.begin(), d.end()); // 高位在前
    return d;
}

// 核心DFS函数
ll dfs(int pos, int state, bool lead, bool limit) {
    // 递归终止条件
    if (pos == digits.size()) {
        return check(state) ? 1 : 0; // 检查状态是否合法
    }
    
    // 记忆化检索（需注意前导零和限制条件）
    if (!lead && !limit && dp[pos][state] != -1) {
        return dp[pos][state];
    }
    
    ll res = 0;
    int up = limit ? digits[pos] : 9; // 当前位上限
    
    for (int d = 0; d <= up; d++) {
        // 处理前导零
        if (lead && d == 0) {
            res += dfs(pos + 1, state, true, limit && (d == up));
        } 
        // 正常状态转移
        else {
            int new_state = update_state(state, d);
            res += dfs(pos + 1, new_state, false, limit && (d == up));
        }
    }
    
    // 记忆化存储（无前导零且无限制时才存储）
    if (!lead && !limit) {
        dp[pos][state] = res;
    }
    return res;
}

// 计算[0, n]满足条件的数字个数
ll solve(ll n) {
    if (n < 0) return 0;
    digits = get_digits(n);
    memset(dp, -1, sizeof(dp)); // 初始化DP数组
    return dfs(0, init_state, true, true);
}

int main() {
    ll L, R;
    cin >> L >> R;
    cout << solve(R) - solve(L - 1) << endl;
    return 0;
}

2.2 关键参数解析

参数	类型	说明
pos	int	当前处理位数（从高位开始）
state	int	压缩的状态信息（如各位和、数字出现情况等）
lead	bool	前导零标志（true表示前面全是0）
limit	bool	上限限制标志（true表示前面位都取到上限）
digits	vector	存储数字的每位（高位在前）

2.3 四大关键函数

1. get_digits()：数字分解
2. dfs()：核心搜索函数
3. update_state()：状态转移（问题相关）
4. check()：终止状态检查（问题相关）

三、经典问题模型与实现

3.1 不含特定数字的个数统计

问题：统计[L,R]范围内不包含4和62的数字个数

状态设计：

• state：记录前一位数字（检查62组合）

实现：

// 状态更新
int update_state(int state, int d) {
    return d; // 只需记录前一位数字
}

// 状态检查
bool check(int state, int d) {
    // 终止时总是合法（检查在转移时完成）
    return true;
}

// 在DFS循环内添加检查
for (int d = 0; d <= up; d++) {
    if (d == 4) continue; // 跳过4
    if (state == 6 && d == 2) continue; // 跳过62
    
    // ... 正常转移
}

3.2 数字和问题

问题：统计[L,R]范围内各位数字之和等于S的数字个数

状态设计：

• state：当前数字和

实现：

const int MAX_SUM = 200; // 最大数字和

// 状态更新
int update_state(int state, int d) {
    return state + d;
}

// 状态检查
bool check(int state) {
    return state == target_sum; // target_sum为预设目标和
}

// 初始化：solve函数中设置target_sum

3.3 数位乘积问题

问题：统计[L,R]范围内各位乘积不超过P的数字个数

状态设计：

• state：当前乘积（需处理前导零）

实现：

// 状态更新
ll update_state(ll state, int d, bool lead) {
    if (lead && d == 0) return 0; // 前导零保持0
    return state * d;
}

// 状态检查
bool check(ll state) {
    return state <= max_product;
}

// 注意：乘积可能很大，需使用map或离散化

四、状态设计高级技巧

4.1 多状态压缩

问题：统计同时满足多个条件的数字个数

示例：统计各位和等于S且不含4的数字

struct State {
    int sum;
    bool has_four;
};

// 状态更新
State update_state(State s, int d) {
    return {
        s.sum + d,
        s.has_four || (d == 4)
    };
}

// 状态检查
bool check(State s) {
    return s.sum == target_sum && !s.has_four;
}

4.2 模数状态

问题：统计满足模运算条件的数字

示例：统计能被M整除且各位和为S的数字

// 状态设计
struct State {
    int sum;
    int mod;
};

// 状态更新
State update_state(State s, int d) {
    return {
        s.sum + d,
        (s.mod * 10 + d) % M
    };
}

// 状态检查
bool check(State s) {
    return s.sum == target_sum && s.mod == 0;
}

4.3 二进制状态压缩

问题：统计包含特定数字集合的数字

示例：统计包含数字集合{2,5,8}的数字

// 状态设计：用9位二进制表示0-9是否出现过
int state = 0;

// 状态更新
int update_state(int state, int d) {
    return state | (1 << d);
}

// 状态检查
bool check(int state) {
    return (state & mask) == mask; // mask= (1<<2)|(1<<5)|(1<<8)
}

五、特殊问题处理技巧

5.1 前导零处理

问题场景：

• 影响数值计算（如乘积）
• 影响数字结构（如回文数）

解决方案：

// 在DFS中
if (lead && d == 0) {
    // 保持前导零状态
    res += dfs(..., true, ...);
} else {
    // 结束前导零
    res += dfs(..., false, ...);
}

5.2 上下界处理

问题：区间[L,R]的统计

解决方案：

ll count(ll n) {
    if (n < 0) return 0;
    digits = get_digits(n);
    memset(dp, -1, sizeof(dp));
    return dfs(0, init_state, true, true);
}

ll result = count(R) - count(L - 1);

5.3 第K大数字查询

问题：求满足条件的第K小数字

解决方案：

ll kth(ll k) {
    ll l = 0, r = MAX_R;
    while (l < r) {
        ll mid = (l + r) / 2;
        if (count(mid) >= k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

六、数位DP优化策略

6.1 状态压缩优化

技巧：合并相似状态

// 原状态：pos(20) × sum(200) × mod(50) = 200,000
// 优化：发现sum只关心与target_sum的差值
int diff = abs(sum - target_sum);
if (diff > MAX_DIFF) diff = MAX_DIFF; // 限制状态数

6.2 双DP优化

问题：同时统计两个相关属性

示例：统计各位和等于S且平方和等于T的数字

// 状态设计
struct State {
    int sum;
    int sq_sum;
};

// 状态更新
State update_state(State s, int d) {
    return {
        s.sum + d,
        s.sq_sum + d * d
    };
}

6.3 数位DP+数学优化

问题：复杂条件统计

示例：统计能被各位和整除的数字

// 状态设计
struct State {
    int sum;
    int mod; // 当前数字模
    int remain; // 当前数字模sum的余数（但sum未知！）
};

// 解决方案：枚举可能的各位和S
for (int s = 1; s <= MAX_SUM; s++) {
    target_sum = s;
    result += solve();
}

七、经典难题解析

7.1 魔法数字（CodeForces 628D）

问题：统计[L,R]内偶数位为d且奇数位不为d的可被M整除的数字

状态设计：

struct State {
    int pos_mod; // 当前模M
    int len;     // 当前长度（判断奇偶位）
};

// 状态转移
State update_state(State s, int d, int pos) {
    int parity = (s.len % 2) == 0; // 0:奇, 1:偶
    if (parity == 1 && d != magic_digit) return invalid;
    if (parity == 0 && d == magic_digit) return invalid;
    
    return {
        (s.pos_mod * 10 + d) % M,
        s.len + 1
    };
}

7.2 数字计数（Luogu P2602）

问题：统计[L,R]内每个数字(0-9)出现的次数

解决方案：对每个数字单独统计

ll count_digit(ll n, int target) {
    // 修改check函数
    auto check = [&](int cnt) { return cnt; };
    
    // 修改状态：当前target计数
    auto update_state = [&](int cnt, int d) {
        return cnt + (d == target);
    };
    
    return solve(n);
}

// 对每个数字0-9
for (int d = 0; d <= 9; d++) {
    cout << count_digit(R, d) - count_digit(L-1, d) << " ";
}

7.3 平衡数（LeetCode 6217）

问题：统计各位数字中不同数字出现次数均为偶数的数字

状态设计：

// 状态：10位二进制，每位表示对应数字出现次数的奇偶性
int state = 0;

// 状态更新
int update_state(int state, int d) {
    return state ^ (1 << d);
}

// 状态检查
bool check(int state) {
    return state == 0; // 所有位出现偶数次
}

八、数位DP扩展应用

8.1 非十进制问题

问题：在B进制下统计满足条件的数字

解决方案：修改数位分解和上限

vector<int> get_digits(ll n, int base) {
    vector<int> d;
    while (n) {
        d.push_back(n % base);
        n /= base;
    }
    reverse(d.begin(), d.end());
    return d;
}

// 在DFS中
int up = limit ? digits[pos] : base - 1;

8.2 负数处理

问题：处理负数范围

解决方案：

// 处理[L,R]的负数范围
if (R < 0) {
    return solve_negative(-L, -R);
} else if (L < 0) {
    return solve_negative(1, -L) + solve_positive(0, R);
}

8.3 浮点数问题

问题：统计满足条件的小数

解决方案：

// 分解整数和小数部分
pair<vector<int>, vector<int>> split(double n) {
    // 整数部分
    ll integer = floor(n);
    // 小数部分
    double frac = n - integer;
    vector<int> frac_digits;
    for (int i = 0; i < precision; i++) {
        frac *= 10;
        frac_digits.push_back(floor(frac));
        frac -= floor(frac);
    }
    return {get_digits(integer), frac_digits};
}

九、性能优化对比

优化策略	时间复杂度	空间复杂度	适用场景
基础数位DP	O(D*S)	O(D*S)	状态空间小
状态压缩	O(D*S’)	O(D*S’)	合并相似状态
双DP优化	O(DS1S2)	O(DS1S2)	多属性统计
枚举各位和	O(SUMDS)	O(D*S)	复杂模运算问题

十、高频面试题精选

1. 数字1的个数（LeetCode 233）
2. 统计特殊整数（LeetCode 2376）
3. 旋转数字（LeetCode 788）
4. 最大为N的数字组合（LeetCode 902）
5. 不含连续1的非负整数（LeetCode 600）
6. 数字转换为16进制（LeetCode 405）变种
7. 统计美丽子数组（LeetCode 6449）

十一、数位DP总结

11.1 核心思维导图

11.2 解题四步法

1. 问题转化：将区间问题转化为[0,N]形式
2. 状态设计：确定需要携带的关键信息
3. 转移方程：定义数位间的状态转移
4. 边界处理：前导零、终止条件等

11.3 学习建议

1. 基础阶段：掌握模板和基本状态设计
2. 进阶阶段：练习多状态压缩问题
3. 高级阶段：攻克数位DP+数学问题
4. 优化阶段：学习状态压缩和剪枝技巧

关键提示：数位DP的核心在于"状态设计"和"前导零处理"。多练习经典问题，培养对状态设计的直觉！

附录：通用数位DP模板（C++17）

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;

using ll = long long;
const int MAX_LEN = 20;

struct DPState {
    bool lead;
    bool limit;
    // 添加自定义状态字段
};

class DigitDP {
private:
    vector<int> digits;
    vector<vector<optional<ll>>>> memo;

    // 初始化状态（根据问题实现）
    DPState init_state() { return {true, true}; }

    // 状态更新（根据问题实现）
    DPState update_state(const DPState& s, int d) {
        bool new_lead = s.lead && (d == 0);
        bool new_limit = s.limit && (d == digits[pos]);
        return {new_lead, new_limit};
    }

    // 终止检查（根据问题实现）
    bool check_state(const DPState& s, int pos) {
        return pos == digits.size();
    }

    // 核心DFS
    ll dfs(int pos, DPState state) {
        if (pos == digits.size()) {
            return check_state(state, pos) ? 1 : 0;
        }
        
        // 记忆化检索
        int state_idx = compress_state(state);
        if (state_idx != -1 && memo[pos][state_idx].has_value()) {
            return memo[pos][state_idx].value();
        }
        
        ll res = 0;
        int up = state.limit ? digits[pos] : 9;
        
        for (int d = 0; d <= up; d++) {
            DPState new_state = update_state(state, d);
            res += dfs(pos + 1, new_state);
        }
        
        // 记忆化存储
        if (state_idx != -1) {
            memo[pos][state_idx] = res;
        }
        return res;
    }

    // 状态压缩（根据问题实现）
    int compress_state(const DPState& s) {
        // 简单示例：返回-1表示不记忆化
        return -1; 
    }

public:
    DigitDP(ll n) {
        // 数字分解
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
        reverse(digits.begin(), digits.end());
        // 初始化记忆化数组
        memo.resize(digits.size(), vector<optional<ll>>(1024));
    }

    ll solve() {
        return dfs(0, init_state());
    }
};

int main() {
    ll L, R;
    cin >> L >> R;
    
    DigitDP dp_l(L-1), dp_r(R);
    ll ans = dp_r.solve() - dp_l.solve();
    
    cout << "Result: " << ans << endl;
    return 0;
}

通过掌握数位DP的核心思想和经典模型，能够高效解决各种数字计数问题。