引入
数位是指把一个数字按照个、十、百、千、万等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 $0\sim 9$。
数位 DP 一般是用来解决一类特定问题，以 1012. Numbers With Repeated Digits (Hard) 为例，这一类问题的特征非常明显
- 要求统计满足一定条件的数的数量；
- 这些条件经过转化后可以使用“数位”的思想去理解和判断；
- 输入会提供一个数字区间（有时候只提供上界）来作为统计的限制；
- 上界很大（例如 $10^{22}$），暴力枚举会超时。
思路
对 1012. Numbers With Repeated Digits (Hard)，思路如下：
首先，正难则反，我们可以考虑 $[1, n]$ 范围内无重复数字的正整数的个数，记为 $res$，然后最终结果就是 $n - res + 1$（至于为什么还要再加上 $1$，后面会说明）。
因此问题转化为求 $[1, n]$ 范围内无重复数字的正整数的个数，符合上述的数位 DP 的特征，我们可以从记忆化搜索的角度去考虑，首先将 $n$ 转化为对应的字符串，对字符串的每一位，枚举每一位可能的数，如果最后组成的数字满足 $num < n$，那么 $res += 1$，这里很容易想到 dfs(string &str, int idx, int mask)，$mask$ 以二进制的形式表示 $0\sim 9$ 范围内的数是否被选择过；
但是仅仅是这样，我们不能方便的判断当前组成的数字是否满足 $num < n$，因此，我们需要一个额外的参数 $is_limit$。例如对数字 $n = 12345$，如果前面已经选择的数字为 $123$，那么对本次枚举，$is_limit$ 为 $true$，即数字只能选择 $0\sim4$，又因为 $1,\ 2,\ 3$ 已经选择了，$mask = 14$，因此只有 $0,\ 4$ 可以选，事实上，我们可以发现，在递归的过程中，当且仅当当前 $is_limit$ 为 $true$，且当前选择的数字与对应数位上的数字相等时，更深一层递归的 $is_limit$ 仍为 $true$，至此，递归函数为 dfs(string &str, int idx, int mask, bool is_limit)；
此外，由于我们递归的终止条件应该是 $idx \geq str.size()$，这样就只能统计出位数与 $n$ 相同的情况，而位数小于 $n$ 的就被忽略了，这是我们不能接受的，因此我们还需要一个参数 $filled$ 来标记之前的位有没有被填充，假设 $filled$ 为 $false$，说明之前没有被填充，那么有两种选择
- 当前位也不填充，
res += dfs(str, idx + 1, false, mask, filled, cach)； - 如果要填充，那么必须从 $1$ 开始填充（因为不能有前导 $0$）,
res += dfs(str, idx + 1, false, mask, true, cach)。
模板
根据以上分析，我们可以总结出一个数位 DP 适用的模板，如下：
int dfs(string &str, int idx, bool is_limit, int mask, bool filled, vector<vector<vector<vector<int>>>> &cach) {
if (idx == str.size()) {
return 1; // 说明找到了一个合理的选择
}
if (cach[idx][is_limit][mask][filled] != -1) {
return cach[idx][is_limit][mask][filled];
}
int limit = is_limit ? str[idx] - '0' : 9;
int res = 0;
if (!filled) {
// 前面的数位都没有填充
res += dfs(str, idx + 1, false, mask, false, cach);
}
int left = filled ? 0 : 1;
for (int i = left; i <= limit; ++i) {
if (((1 << i) & mask) != 0) {
// 说明 i 已经选择过了
continue;
}
res += dfs(str, idx + 1, is_limit && (i == str[idx] - '0'), mask | (1 << i), true, cach);
}
cach[idx][is_limit][mask][filled] = res;
return res;
}
在这个模板中，由于所有位都不填，也会被统计进结果中，因此 $res$ 比实际的 $res$ 多了 $1$，我们可以在最后计算的时候减去 $1$，也可以把边界条件的返回值修改为如下：
if (idx == str.size()) {
return is_num; // is_num 为 true 说明找到了一个合法的数字，为 false 说明所有位都不填
}