数位动态规划（数位dp）主要用于解决“在区间 [l, r] 这个范围内，满足某种约束的数字的数量、总和、平方”这一类问题
前置知识：位运算与集合论
集合可以用二进制表示，二进制从低到高，第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。例如集合 {0, 2, 3} 对应的二进制数为 1101 。
设集合对应的二进制数为 x ：
- 判断元素
d是否在集合中：x >> d & 1可以取出x的第d个比特位，如果是 1 就说明d在集合中。 - 把元素
d添加到集合中：将x更新为x | (1 << d)。
下面用一道题来介绍数位 dp 的通用模板
统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。
示例 3：
输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 10^9
思路
将 n 转换成字符串 s ，定义：dfs(i, mask, isLimit, isNum) 表示构造第 i 位及其之后数位的合法方案数，其余参数的含义为：
mask表示前面选过的数字集合，换句话说，第i位要选的数字不能在mask中。isLimit表示当前是否受到了n的约束（注意要构造的数字不能超过n）。若为true，则第i位填入的数字至多为s[i]，否则可以是 9 。如果在受到约束的情况下填了s[i]，那么后续填入的数字仍然会受到n的约束。例如n = 123，如果i = 0填的是 1 的话，i = 1的这一位至多填 2 。如果i = 0填的是 1，i = 1填的是 2，那么i = 2的这一位至多填 3 。isNum表示i前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；若为真，则要填入的数字可以从 0 开始。例如n = 123，在i = 0时跳过的话，相当于后面要构造的是一个 99 以内的数字了，如果i = 1不跳过，那么相当于构造一个 10 到 99 的两位数字，如果i = 1跳过，相当于构造的是一个 9 以内的数字。- 为什么要定义
isNum？因为010和10都是10，如果认为第一个 0 和第三个 0 都是我们填入的数字，就不符合题目每位数字都不重复的要求了，但10显然符合题目要求。
实现细节
递归入口：dfs(0, 0, true, false) ，表示：
i = 0：从s[0]开始枚举；mask = 0：一开始集合中没有数字（空集）；isLimit = true：一开始要受到n的约束（否则就可以随意填了）；isNum = false：一开始没有填数字。
递归过程：
- 如果
isNum为false，说明前面没有填数字，那么当前也可以不填数字。一旦从这里递归下去，isLimit就可以置为false了，这是因为s[0]必然是大于 0 的，后面就不受到n的约束了。或者说，最高位不填数字，后面无论怎么填都比n小。 - 如果
isNum为true，那么当前必须填一个数字。于是乎我们可以枚举当前位填入的数字，根据isNum和isLimit来决定填入数字的范围。
递归终点：当 i 等于 s 的长度时，如果 isNum 为 true ，则表示得到了一个合法的数字（不合法的数字不会递归到终点），返回 1，否则返回 0 。
Code
class Solution {
public:
int countSpecialNumbers(int n) {
string s = to_string(n);
int m = s.length();
vector<vector<int>> memo(m, vector<int>(1 << 10, -1)); // -1 表示当前位没有计算过
auto dfs = [&](auto&& dfs, int i, int mask, bool is_limit, bool is_num) -> int {
if (i == m) { // 递归边界
return is_num; // is_num 为 true 表示得到了一个合法数字
}
if (!is_limit && is_num && memo[i][mask] != -1) {
return memo[i][mask]; // 记忆化，之前计算过直接返回
}
int res = 0;
if (!is_num) { // 当前位前面均跳过，因此当前位也可以跳过
res = dfs(dfs, i + 1, mask, false, false);
}
// 如果前面填的数字都和 n 对应位一样，那么这一位至多填数字 s[i]
int up = is_limit ? s[i] - '0' : 9;
// 枚举当前位需要填的数字
// 如果前面没有填数字，则必须从 1 开始（不能有前导零）
for (int d = is_num ? 0 : 1; d <= up; ++d) {
if ((mask >> d & 1) == 0) { // d 不在 mask 中，说明之前没有填过 d
res += dfs(dfs, i + 1, mask | (1 << d), is_limit && d == up, true);
}
}
if (!is_limit && is_num) {
memo[i][mask] = res; // 记忆化
}
return res;
};
return dfs(dfs, 0, 0, true, false);
}
};