很典型的数位dp，把全球第一的代码拿过来研究了一下，加了点注释
代码作者：waakaaka
个人主页：https://leetcode.com/waakaaka/
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define db(x) cerr << #x << "=" << x << endl 4 #define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl 5 #define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl 6 #define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl 7 #define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl 8 typedef long long ll; 9 typedef long double ld; 10 class Solution 11 { 12 public: 13 int n; 14 int dis; 15 //val为当前数值，bs可以看作是vector<int> hash(10) 16 void go(ll val, int bs) 17 { 18 // 当前数值小于题目所给n，非重复的结果数++ 19 if (val <= n) ++dis; 20 //当前数值乘以10大于所给n，直接返回，不然进了下面的循环就乘以10继续递归了 21 if (val * 10 > n) return; 22 for (int i = 0; i <= 9; ++i) 23 { 24 //当前数值为0（bs为零等价于val为零）且加的一个数字还是零，就直接continue，因为不支持前缀零 25 if (!bs && i == 0) continue; // no 0 for first digit 26 //如果要加的数字i和已经有的数字重复，就也continue，不进行递归 27 if (bs & (1 << i)) continue; 28 //加上尾数i，然后更新状态bs，继续递归 29 go(val * 10 + i, bs | (1 << i)); 30 } 31 } 32 int numDupDigitsAtMostN(int N) 33 { 34 dis = 0; 35 n = N; 36 go(0, 0); 37 //dis为不重复的数字的个数 38 return N + 1 - dis; 39 } 40 };