数位动态规划（数位dp）主要用于解决“在区间 [l, r] 这个范围内，满足某种约束的数字的数量、总和、平方”这一类问题

前置知识：位运算与集合论

集合可以用二进制表示，二进制从低到高，第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。例如集合 {0, 2, 3} 对应的二进制数为 1101 。

设集合对应的二进制数为 x ：

1. 判断元素 d 是否在集合中：x >> d & 1 可以取出 x 的第 d 个比特位，如果是 1 就说明 d 在集合中。
2. 把元素 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);
    }
};