class Solution {
public:
    int countSpecialNumbers(int n) {
        auto s = to_string(n); // 把上限 n 转化为字符串
        int m = s.length(), dp[m][1 << 10]; // dp数组, 记忆化搜索需要使用, 代表 不受约束时 填了数 (先导 0 不算) 考虑了 0 - i 位, 所用数字为 mask 的数字个数. 需要注意的是, 只用二维存储, 但含义是四维的, 在递归函数中做进一步解释
        memset(dp, -1, sizeof(dp)); // dp数组初始化
        function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int { // 递归函数
            if (i == m) return is_num; // i == m, 所有数位已经填完了, 如果是 is_num 为 true, 说明答案填了数, 返回 1 ; 否则说明考虑的是 0 (每一位都没有天数)
            if (!is_limit && is_num && dp[i][mask] >= 0) return dp[i][mask]; // 满足 dp 定义才能调用已有结果, 参考 dp 数组的含义
            int res = 0; // 计算新结果
            if (!is_num) res = f(i + 1, mask, false, false); // 可以跳过当前数位
            for (int d = 1 - is_num, up = is_limit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
                if ((mask >> d & 1) == 0) // d 不在 mask 中
                    res += f(i + 1, mask | (1 << d), is_limit && d == up, true); // 填入 d , 后续的位数变化, mask变化, is_limit 由 前面位是否为上限 以及 d 是否为该位上限 共同决定, 因为填了数, is_num 为 true 
            if (!is_limit && is_num) dp[i][mask] = res; // 如果不受 n 限制, 并且填了数, 就记忆化
            return res;
        };
        return f(0, 0, true, false); // 从最高位开始填, 一开始一个没有填, 受到 n 限制, 还没有填 的数的个数
    }
};