leetcode 1015. Numbers With Repeated Digits
题意:统计1-N中，满足每个位置都不同的数有几个。
思路：数位DP。通过一个1<<10的mask表示当前这个数，1-9哪些数被用了。
比赛的时候，一直想通过一个dfs直接找到不重复的数，一直不对。
赛后发现，别人都是通过一个dfs找重复的数，然后总个数减去。
class Solution {
public:int numDupDigitsAtMostN(int N) {int sum = N + 1;memset(bit, 0, sizeof(bit));memset(dp, 0, sizeof(dp));int k = 0;while (N) {bit[++k] = N % 10;N /= 10;}return sum - dfs(k, true, 0);}//不重复数的个数int dfs(int len, bool limit, int mask) {if (len == 0)return 1;if (!limit && dp[len][mask][limit]) return dp[len][mask][limit];//记忆化部分int maxn = limit ? bit[len] : 9;//求出最高可以枚举到哪个数字int ans = 0;for (int i = 0; i <= maxn; i++) //当前位{if ((mask&(1 << i)) == 0){if (mask == 0 && i == 0)ans += dfs(len - 1, limit && i == maxn, mask);//有前导0,所以0不能统计,不更新maskelseans += dfs(len - 1, limit && i == maxn, mask | (1 << i));//更新mask}}if (!limit) dp[len][mask][limit] = ans;//如果没有限制,代表搜满了,可以记忆化,否则就不能return ans;}
private:int bit[19];int dp[19][1 << 10][2];};