【考点 · 8级】数位DP，属于动态规划 + 位运算思想的交叉考点。
【说人话】
数位DP的核心思路是：把一个数拆成从高位到低位的每一位，逐位讨论。每一位可以「填小于上限的数（后面随便填）」或「填等于上限的数（继续卡上限）」。
关键变量：
pos：当前处理到第几位（从高位往低位走）limit：是否还在「卡上限」——如果前面已经比上限小了，后面每一位都可以填 0~9state：题目需要的状态，比如「上一位填了什么」「数字之和」等模板思路：f(pos, limit, state) 表示从第 pos 位开始，在 limit 约束下，当前状态为 state 的合法方案数。
limit 为 true 时，当前位只能填 0 到 digit[pos]；limit 为 false 时，可以填 0 到 9。每次递归时把 limit 传递下去。
经典题目：统计 [1, N] 中不含前导零、且相邻两位数字不同的正整数个数
数位DP中，limit 变量的作用是什么？
为什么 limit=true 时不能直接用记忆化结果？
统计 [L, R] 范围内的答案，公式是什么？
sum 状态表示当前已用的数字之和。当 sum > S 时提前剪枝。最终当 pos < 0 时，判断 sum == S。
#include <bits/stdc++.h>
using namespace std;
long long N;
int S, digits[20], dp[20][163];
int len;
long long dfs(int pos, int sum, bool limit) {
if (sum > S) return 0; // 剪枝：超出目标和
if (pos < 0) return sum == S; // 到末位，判断是否恰好等于S
if (!limit && dp[pos][sum] != -1)
return dp[pos][sum]; // 记忆化（无limit才缓存）
int up = limit ? digits[pos] : 9;
long long ans = 0;
for (int i = 0; i <= up; i++)
ans += dfs(pos - 1, sum + i, limit && i == up);
if (!limit) dp[pos][sum] = ans;
return ans;
}
long long solve(long long n) {
len = 0;
while (n) { digits[len++] = n % 10; n /= 10; }
memset(dp, -1, sizeof(dp));
return dfs(len - 1, 0, true);
}
int main() {
cin >> N >> S;
cout << solve(N) << endl;
}
pre 状态换成 sum（数字之和），其余框架完全一样。注意 sum > S 提前返回0是关键剪枝，不然会超时。
lead 变量区分limit=true 的结果依赖于原数每一位的值，直接缓存会算错limit=false 的结果，即 dp[pos][state][0]n % 10 存入 digits[0]，即低位在前，从 len-1 往 0 递归