众所周知，数位 dp 是一种难写难调的 sb dp，这里记录一种便于调试的写法。
- 对于一个区间询问 \([a,b]\)，可以把它拆分成 \([1,b]\) 和 \([1,a-1]\) 两个部分作差，并使用函数 \(solve(x)\) 计算出 \([1,x]\) 的答案，将答案的形式改写为 \(solve(b)-solve(a-1)\) 以减小码量；
- 对于状态转移与答案输出，使用记忆化搜索，其明显简单于直接循环 dp；
- 对于一个数的表示，直接用
vector存储也许会方便很多。
示例代码：
// 题目名称：不要 62
int dfs(int x, int lst, bool op)
// x 表示当前枚举位置，lst 表示上一个数，op 表示该数是否有限制
{
if (!x) return 1;
if (!op && ~dp[x][lst]) return dp[x][lst];
int mx = op ? num[x] : 9, tot = 0;
rep(i, 0, mx) {
if (i == 4) continue;
if (lst == 6 && i == 2) continue;
tot += dfs(x - 1, i, op && i == mx);
}
if (!op) dp[x][lst] = tot;
return tot;
}
int solve(int x)
{
num.clear();
num.emplace_back(-1); // 空位置
while (x) num.emplace_back(x % 10), x /= 10;
return dfs(num.size() - 1, 0, 1);
}
本篇博客只讲了写法，只因我是一个鸽子（咕咕咕）。。。