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

题目：

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

示例 1：

输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。

示例 2：

输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。

示例 3：

输入：n = 1000
输出：262

提示：

1 <= n <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/numbers-with-repeated-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

题目要求至少含1位重复数字的方案数，那显然等价于总数N-不含任何重复数字的方案数，然后就可以用数位DP去求不含任何重复数字的方案数
设dp[pos][st]表示正在考虑第pos位，此时数字的使用状态已经是st，且不含重复数字的方案数。
那么显然dp[pos][st] += dp[pos-1][st|(1< 当然最后可能存在全部都是0这种完全由前导0构成的非法方案，所以当搜到最底层返回时要用st来判断一下当前数字是否是存在的，不存在就得返回0。
注意下位运算的优先级

代码：

class Solution
{
public:static const int N = 10;int dp[N][1 << N]; int a[N], n;int dfs(int pos, int st, int lead, int lim){if(pos <= -1)return !st ? 0 : 1;if(!lead && !lim  && ~dp[pos][st])return dp[pos][st];int up = lim ? a[pos] : 9;int ret = 0;for (int i = 0; i <= up; ++i){if(i == 0){if(!lead){if(!(st >> i & 1))ret += dfs(pos - 1, st | (1 << i), lead && i == 0, lim && i == a[pos]);}else{ret += dfs(pos - 1, st, lead && i == 0, lim && i == a[pos]);}}else{if(!(st >> i & 1)){ret += dfs(pos - 1, st | (1 << i), lead && i == 0, lim && i == a[pos]);}}}if(!lead && !lim)dp[pos][st] = ret;return ret;}int numDupDigitsAtMostN(int N){n = 0;int num = N;do {a[n++] = num % 10;num /= 10;}while (num);memset(dp, -1, sizeof(dp));int diff = dfs(n - 1, 0, 1, 1);return N - diff;}
};

作者：codefresher
链接：https://leetcode.cn/problems/numbers-with-repeated-digits/solution/shu-wei-dpru-men-ti-by-codefresher-9w0o/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。