1012. 至少有 1 位重复的数字

题目链接：1012. 至少有 1 位重复的数字

方法：数位dp

解题思路

参考：数位 DP 通用模板，附题单（Python/Java/C++/Go）
注意：其中\(isNum\)是用来针对前导\(0\)可能影响结果而设置的标志，如\(010\)（即\(10\)）实际是没有重复的数字，而由于前导\(0\)的影响使得是有重复的数字。对于不受前导\(0\)影响的数位\(dp\)，则不需要设置\(isNum\)标志，例如：
233.数字 1 的个数
面试题 17.06. 2出现的次数

代码

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        int m = s.length(), cache[m][1 << 10]; // 记忆化i：当前的位置 和 mask：二进制掩码，判断哪些数字被用过，记录该种情况下的数量，使得不用继续递归下去做重复的计算。
        memset(cache, -1, sizeof(cache));
        function<int(int, int, bool, bool)> f = [&](int i, int mask, bool isLimit, bool isNum) -> int {
            if (i == m) return isNum; // isNum == true，表示当前组成的数字合法
            if (!isLimit && isNum && cache[i][mask] != -1) return cache[i][mask];
            int res = 0;
            if (!isNum) res = f(i + 1, mask, false, false);
            int up = isLimit ? s[i] - '0' : 9;
            for (int d = 1 - isNum; d <= up; d ++ ) {
                if ((mask >> d & 1) == 0) 
                    res += f(i + 1, mask | (1 << d), d == up && isLimit, true);
            }
            if (!isLimit && isNum) cache[i][mask] = res;
            return res;
        };
        return n - f(0, 0, true, false);
    }
};