数位 DP 入门
最近一直在刷数位 DP 的题，于是写这篇博客总结一下。
本质
数位 DP 与其说是 DP 不如说是一种记忆化搜索的思路。
看到求 $[L, R]$ 间满足某个性质的数有多少个，并且 $L, R$ 很大的时候可能就需要用到这个方法。
由于同时处理上下界的搜索会非常麻烦，所以需要小小差分一下，也就是利用 $[0/1, R]$ 满足性质的数减去 $[0/1, L)$ 满足性质的数。
是否需要 $0/1$ 依据题意而言。
思想
搜索是从高位开始向低位填数。所填之数需要存在一个性质或者状态与填数的方案无关，也就是无论填什么数，只要满足这个性质，后面都可以填相同的数。
入门题
如果一个正整数的二进制表示中，$0$ 的数目不小于 $1$ 的数目，那么它就被称为「圆数」。
例如，$9$ 的二进制表示为 $1001$，其中有 $2$ 个 $0$ 与 $2$ 个 $1$。因此，$9$ 是一个「圆数」。
请你计算，区间 $[l,r]$ 中有多少个「圆数」。
分析：
需要存在的性质与 $0, 1$ 的个数只差有关，所以状态可以设为个数之差。
可以发现只要差一样，那么后面可以填的数的个数相同。
这满足记忆化的要求，所以可以上搜索。
但是我们会发现前导零会对答案造成影响，所以需要加上一个参数来表示是否有前导零的存在，也就是参数中的 zero。
// 由于 d 可能为负数，所以需要加上一个 OFFSET 强制转化为正数
int dfs(int p, int d, bool zero, bool up) {
if (p == 0) return d >= 0;
if (!up && !zero && ~f[p][d + OFFSET]) {
return f[p][d + OFFSET];
}
int res = 0;
for (int i = 0, ie = up ? s[p] : 1; i <= ie; ++i) {
res += dfs(p - 1, i ? d - 1 : (zero ? d : d + 1), zero && (i == 0), up && (i == ie));
}
if (!up && !zero) f[p][d + OFFSET] = res;
return res;
}
到这里，只是思想上，实现上还有很多问题。
如何保证是在上界内？
首先我们将目标数按照需要的进制进行拆分：
int solve(int M) {
memset(f, -1, sizeof(f));
int len = 0;
while (M) {
s[++len] = M & 1;
M >>= 1;
} return dfs(len, 0, true, true);
}
然后在 dfs 时利用 up 判断是否抵着上界在搜索即可。