题目链接：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);
}
};