数位dp
作者:
张先森
,
2024-01-22 00:37:36
,
所有人可见
,
阅读 49
class Solution {
string s = "";
public:
// x 枚举到第几位,mask 用过的位 标为1,
//is_num表示前面是不是填了数字,is_limit表示前面的位是不是达到了最大值
int dfs(int x, int mask, bool is_limit, bool is_num) {
if(x == s.size()) return (int)is_num;
int res = 0;
if(!is_num) {
// 没填数字 可以跳过
res = dfs(x + 1, mask, false, false);
}
int up = 0;
if(is_limit) up = s[x] - '0';
else up = 9;
for(int i = 1 - is_num; i <= up; i ++) {
if((mask >> i & 1) == 0) {
res += dfs(x + 1, mask | (1 << i), is_limit & (i == up), true);
}
}
return res;
}
int countSpecialNumbers(int n) {
while(n) {
s.push_back(n % 10 + '0');
n /= 10;
}
reverse(s.begin(),s.end());
int res = dfs(0, 0, true, false);
return res;
}
};