潘木禾1. 数位DP概述
数位动态规划（Digit Dynamic Programming）是一种专门用于解决与数字各位相关问题的算法技巧。它通常用于统计满足特定条件的数字数量，或者计算数字的某些特性。这类问题的共同特点是：
- 输入通常是一个非常大的数字范围（比如1到10^100）
- 条件与数字的各位数字有关
- 直接暴力枚举所有数字并检查条件会超时
数位DP的核心思想是将数字看作由各位组成的序列，然后按位进行处理，同时利用动态规划来避免重复计算。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 数位DP的基本原理
2.1 数字的分解表示
数位DP的关键在于将数字分解为各位数字的组合。例如，数字1234可以表示为：
- 千位：1
- 百位：2
- 十位：3
- 个位：4
这种分解方式让我们可以逐位处理数字，而不是将其作为一个整体。
2.2 状态设计
典型的数位DP状态包含以下维度：
- 当前处理到的位数（pos）
- 前导零状态（lead）
- 是否已经小于上界（limit）
- 问题特定的状态（如数字出现的次数、特定模式等）
状态表示通常为：dp[pos][state][lead][limit]
2.3 记忆化搜索
数位DP通常采用记忆化搜索（Memoization）的方式实现，这比迭代式的动态规划更直观。记忆化搜索的框架如下：
cpp复制int dfs(int pos, int state, bool lead, bool limit) {
if(pos == -1) return check(state); // 处理完所有位数
if(!limit && !lead && dp[pos][state] != -1)
return dp[pos][state]; // 记忆化
int res = 0;
int up = limit ? digit[pos] : 9; // 当前位的上限
for(int i = 0; i <= up; i++) {
// 根据当前数字i更新状态
int new_state = update_state(state, i);
bool new_lead = lead && (i == 0);
bool new_limit = limit && (i == up);
res += dfs(pos-1, new_state, new_lead, new_limit);
}
if(!limit && !lead) dp[pos][state] = res; // 记录状态
return res;
}