什么是数位 DP
数位 DP 是处理”大范围内按数位统计数字”问题的动态规划技术。典型问题：统计区间 [L, R] 内有多少个数字不含某个数字、不含连续 “62”、各位数字之和满足某条件等。当范围达到 10¹⁸ 级别时无法暴力枚举，而数位 DP 把复杂度降到与位数相关的多项式级别，是这类题的通用解法。
核心思想
把数字从高位到低位逐位处理。关键在于三个状态维度：
- pos：当前处理到哪一位；
- limit：当前位是否受上限约束——比如上限 123，处理到十位时若已取 1（等于上界），个位最多只能取 3，否则可以取 0–9。受约束的状态不能记忆化，因为它依赖具体上界；
- lead：前面是否全是前导零——影响”0 是否算数位”等判断；
- 其他自定义状态：如前一位数字
pre、数字和sum等。
通用模板（C++）
typedef long long ll;
int a[20]; // 按位存上限
ll dp[20][state]; // state 按问题定义
ll dfs(int pos, int state, bool lead, bool limit) {
if (pos == -1) return 1; // 处理完，返回有效计数（按问题调整）
if (!limit && !lead && dp[pos][state] != -1)
return dp[pos][state]; // 只有"不受限"状态才记忆化
int up = limit ? a[pos] : 9;
ll res = 0;
for (int i = 0; i <= up; i++) {
if (/* 问题特定条件，如 i==4 */) continue;
res += dfs(pos-1, /* 新状态 */, lead && i == 0, limit && i == up);
}
if (!limit && !lead) dp[pos][state] = res;
return res;
}
ll solve(ll x) {
int pos = 0;
while (x) { a[pos++] = x % 10; x /= 10; } // 低位存到高位
memset(dp, -1, sizeof(dp));
return dfs(pos-1, /* 初始状态 */, true, true);
}
// 区间 [L, R] 的答案 = solve(R) - solve(L-1)
经典例题
- 不要 62（HDU 2089）：统计不含数字 4、且不含连续 “62” 的数字个数。状态记录”前一位是否为 6″，当前位为 2 且前一位是 6 时跳过；
- 数字 1 的个数（LeetCode 233）：统计 1..n 中所有数字里 1 出现的总次数；
- windy 数（BZOJ 1026）：相邻两位之差至少为 2 的数字个数，状态记录前一位数值。
优化技巧
- 状态压缩：需要记录”0–9 是否出现过”时，用一个 10 位 bitmask 作为状态；
- 多约束合并：多个限制条件可以并进同一个状态维度，减少 DP 数组规模；
- 注意 lead 的处理：前导零状态通常与正常状态分开记忆化，避免混淆”0 前面没有数字”和”前一位是 0″。
复杂度分析
- 时间：O(位数 × S × 10)，S 为状态数。对 10¹⁸ 的数据，位数约 19，实际运算量极小；
- 空间：O(位数 × S)。
数位 DP 的价值在于把”逐个数数字”的指数级暴力，变成”按位枚举 + 状态复用”的多项式算法——看到”统计 [L, R] 内满足条件的数字个数”这类题，优先想到它。