一、定义
求出在给定区间 [A,B] 内，符合条件 f(i) 的数i的个数。条件f(i)一般与数的大小无关，而与数的组成有关。由于数是按位dp，数的大小对复杂度的影响很小。
简单来说，就是解决一些与区间中的数字的计数问题，计数条件一般与数的组成有关。
二、状态量
一般采用记忆化搜索的方式来实现dp，dp的状态经常包括pos、pre、cnt、lead、limit这几项：
- pos：当前处理的是数位的第几项，一般从高往低走
- pre：当前位的前几位的状态，由于数位dp解决的大多是数字组成问题，所以经常要比较当前位和前一位或前几位的关系（根据题意而定）
- cnt：随着pos的前进需要维护的一些答案值/计数值
- lead：当前位是否位前导0位
- limit：当前位的最大值是否存在限制
三、记忆化搜索
把dfs的答案值存放在dp[pos][pre][cnt][...]数组中，以避免重复计算。
原理：从pos开始的低位dp答案会在高位值的枚举遍历中被反复调用。若从某个pos开始的dp它的前置状态pre和之前的某一次处理完全一样，则无需再重复计算，直接返回之前的答案值即可。因为所拥有的条件和上一次完全一样。
注意：当当前位为前导0或当前位受到限制时，没有必要将该值记录到dp数组。因为这些状态并不会被重复使用。
四、模板
以下模板大多数情况可套用，但部分细节还是需要结合具体题意进行考虑。
ll a[20], dp[20][20]; // a是用来装数位最高值的数组，dp是memo数组
ll dfs(ll pos, ll pre, ll cnt, bool lead, bool limit) {
if(pos == 0) return cnt; // 已经遍历完一个数的情形
if(!lead && !limit && dp[pos][pre][...] != -1) return dp[pos][pre][...]; // 记忆化搜索
ll res = 0, maxv = limit ? a[pos] : 9; // 计算当前位最大值
for(ll i = 0; i <= maxv; i ++) {
// 若当前位是前导0
if(i == 0 && lead) res += dfs(pos - 1, ...., 1, limit && i == maxv);
// 若当前位是最高位
else if(i && lead) res += dfs(pos - 1, ...., 0, limit && i == maxv);
// 正常情况
else res += dfs(pos - 1, ...., 0, limit && i == maxv);
}
if(!lead && !limit) dp[pos][cnt] = res;
return res; // 注意区分res和cnt，res是问题的答案，cnt是当前状态维护的小答案，res由最终的cnt累加而成
}
ll cal(ll num) {
ll pos = 0;
while(num) a[++ pos] = num % 10, num /= 10; // 把数按位拆分（数位dp的前提）
memset(dp, -1, sizeof(dp)); // memo数组初始化为-1
return dfs(pos, 0, 1, 1); // 从高位往低位dp
}
int main() {
......
// 注意！！！l为0时一般要特别处理，因为数位dp的过程会将0一直当作前导0从而忽略了数值0这一个数，不过由于是计算差值所以大部分情况不影响
cout << cal(r, i) - cal(l - 1, i); // 将区间计算转化为差值计算
......
}五、例题
Nowcoder 17867：https://blog.nowcoder.net/n/616849ad0fc14a69b57af2e4e78191fc
ZJOI 2010：https://blog.nowcoder.net/n/4d0c2930acc84d6c97c2e356edaeb7cd
数位dp就是模板题！！！
京公网安备 11010502036488号