数位 DPCSP-S

💡 核心思想

数位 DP 用于解决"从 $a$ 到 $b$ 的所有整数中，满足某条件的数有多少个"这类计数问题。核心思想是按数位逐位处理，用"是否有前导限制（limit）"和"是否有前导零"来定义状态。

🎯 直觉理解

想象你要数从 1 到 1000 里有多少个含"7"的数。你不是逐个检查，而是按位分析：第1位（个位）是7的概率、第2位是7的概率……数位 DP 就是按位计数，避免遍历每个数。

📝 算法流程

1. 将数字按位分解
2. DFS 记忆化：枚举当前位可以取的值
3. limit 和 lead 状态不记忆化
4. 结果 = solve(b) - solve(a-1)

$$\text{ans} = \text{count}(b) - \text{count}(a-1)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 数位DP模板：[1,n]中不包含数字4的个数
string num; int m;
int dp[15][2];
int dfs(int pos, bool limit, bool lead) {
    if (pos == m) return lead ? 0 : 1;
    if (!limit && !lead && dp[pos][0] != -1) return dp[pos][0];
    int up = limit ? num[pos]-'0' : 9;
    int ans = 0;
    if (lead) ans += dfs(pos+1, limit && 0==up, true);
    for (int d = (lead ? 1 : 0); d <= up; d++) {
        if (d == 4) continue; // 不包含4
        ans += dfs(pos+1, limit && d==up, false);
    }
    if (!limit && !lead) dp[pos][0] = ans;
    return ans;
}
int count(int n) {
    num = to_string(n); m = num.size();
    memset(dp, -1, sizeof(dp));
    return dfs(0, true, true);
}
int main() {
    int n; cin >> n;
    cout << count(n) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目