C++/Python, digit dp solution with explanation
find how many number without repeated digits\nfill a number digit by digit.\ni means we are filling i-th digit.\nmask is number we used in the number, it is a b
### find how many number without repeated digits\nfill a number digit by digit.\ni means we are filling i-th digit.\nmask is number we used in the number, it is a bitmask, means which number we have used in [0,9].\nis_limit means the current number is on the upper bound, e.g., n = 234, and digit is 23, we are filling last number -> 23[4].\nhas_leading0s means digits are all 0s, e.g., 000, and we can fill a valid digit or skip it (fill a 0).\n\nfor i-th digit,\nif has_leading0s is true, we can skip i-th digit, keep has_leading0s\nor fill a digit in [1,9],\nif has_leading0s  is true, digit can not be 0\nif is_limit is true, digit is at most int(s[i]).\n\neumerate digit from low to high,\nif this digit is not repeated, we can fill next digit.\n\n\n### python\n```python\nclass Solution:\n    def numDupDigitsAtMostN(self, n: int) -> int:\n        s = str(n)\n        @cache\n        def dfs(i, mask, is_limit, has_leading0s):\n            if i == len(s): return int(not has_leading0s)\n            sub = 0\n            if has_leading0s:\n                sub = dfs(i+1, mask, False, True)\n            low = 1 if has_leading0s else 0\n            high = int(s[i]) if is_limit else 9\n            for d in range(low, high+1):\n                if mask >> d & 1 == 0:\n                    sub += dfs(i+1, mask | (1 << d), is_limit and d == high, False)\n            return sub\n        \n        return n - dfs(0, 0, True, True)\n```\n\n### c++\n```cpp\nclass Solution {\npublic:\n    int numDupDigitsAtMostN(int n) {\n        string s = to_string(n);\n        vector<vector<int>> dp (s.size(), vector<int>(1<<10, -1));\n        function<int(int, int, bool, bool)> dfs = [&] (int i, int mask, bool is_limit, bool leading0s) {\n            if (i == s.size()) return (int)!leading0s;\n            if (!is_limit && !leading0s && dp[i][mask] != -1) return dp[i][mask];\n            int sub = 0;\n            if (leading0s) sub = dfs(i+1, mask, false, true);\n            int low = leading0s? 1:0, high = is_limit? s[i]-\'0\': 9;\n            for (int d = low; d <= high; d+=1) {\n                if ((mask >> d & 1) == 0) {\n                    sub += dfs(i+1, mask | (1<<d), is_limit && d == high, false);\n                }\n            }\n            if (!is_limit && !leading0s) dp[i][mask] = sub;\n            return sub;\n        };\n        return n - dfs(0, 0, true, true);\n    }\n};\n```\n\n### find how many number at least one repeated digit\n\nfill a number digit by digit.\n\nhas_repeated means digits we filled has at least one repeated digit.\n\n\n\n### python\n```python\nclass Solution:\n    def numDupDigitsAtMostN(self, n: int) -> int:\n        s = str(n)\n        @cache\n        def dfs(i, mask, is_limit, leading0s, has_repeated):\n            if i == len(s): return int(has_repeated)\n            sub = 0\n            if leading0s: sub = dfs(i+1, mask, False, True, False)\n            low = 1 if leading0s else 0\n            high = int(s[i]) if is_limit else 9\n            for d in range(low, high+1):\n                sub += dfs(i+1, mask | (1 << d), is_limit and d == high, False, has_repeated or mask >> d & 1 == 1)\n            return sub\n        return dfs(0, 0, True, True, False)\n```\n\n### c++\n```cpp\nclass Solution {\npublic:\n    int numDupDigitsAtMostN(int n) {\n        string s = to_string(n);\n        vector<vector<vector<int>>> dp (s.size(), vector<vector<int>>(1<<10, vector<int>(2, -1)));\n        function<int(int, int, bool, bool, bool)> dfs = [&] (int i, int mask, bool is_limit, bool leading0s, bool has_repeated) {\n            if (i == s.size()) return (int) has_repeated;\n            if (!is_limit && !leading0s && dp[i][mask][(int) has_repeated] != -1) return dp[i][mask][(int) has_repeated];\n            int sub = 0;\n            if (leading0s) sub = dfs(i+1, mask, false, true, false);\n            int low = leading0s? 1:0, high = is_limit? s[i] - \'0\': 9;\n            for (int d = low; d <= high; d+=1)\n                sub += dfs(i+1, mask | (1 << d), is_limit && d == high, false, has_repeated || mask >> d & 1);\n            if (!is_limit && !leading0s) dp[i][mask][(int) has_repeated] = sub;\n            return sub;\n        };\n        return dfs(0, 0, true, true, false);\n    }\n};\n```
['Dynamic Programming', 'C', 'Python']