数位dp通常的设问方式是区间[l, r]中的整数，满足条件的有多少个，并且该条件与数位有关。
可以利用前缀和思想来转换问题，先求解[1, l-1]和[1, r]，进而求解[l, r] = [1, r] - [1, l-1]。
首先将数x按照进制b转换，并且将转换的数存到数组a[1...len]中（1存低位，len存高位）。
int len = 0;
while (x) {
a[++len] = x % b;
x /= b;
}
初始化dp数组f[1...len][...]为全-1，数组f[i][j]表示a[len...i+1]不贴上界、无前导零，并且前序信息为pre时，满足条件的整数有多少个。
// led判断该数位是否需要考虑前导零问题（也即前序数位是否全为零）
// lmt判断该数位是否有取值限制（也就是前序数位是否贴着上界，即正好等于x的前序数位）
// pre记录前序数位信息（常见的如：前一数位的值，前序数位之和，某数出现次数等）
int dfs(int pos, int lmt, int led, int pre) {
if (!pos) { // 到达递归边界
// 此时已将该数按数位从高到低扫了一遍
// pre记录扫描完该数后得到的数位信息
// led记录该数是否为0（前导零标记仍然为1说明所有数位都是0）
return 某值; // 可以参考pre和led的情况确定返回值
}
if (!lmt && !led && f[pos][pre] != -1) // 只有不贴上界，无前导零才是可复用的
return f[pos][pre]; // 剪枝，对于已经求解过的直接返回
int res = 0, up = lmt ? a[pos] : b-1; // up为当前数位上界
for (int i = 0; i <= up; i ++) {
if (满足剪枝条件)
continue;
res += dfs(pos-1, lmt && i==up, led && !i, pre更新);
}
if(!lmt && !led) // 只有不贴上界，无前导零才是可复用的
f[pos][pre] = res; // 将res存储到dp数组中
return res;
}
调用dfs实现记忆化搜索，可以得到[1, x]中满足条件的整数有多少个。
dfs(len, 1, 1, pre初值);