C++ | Standard Digit DP
This is a standard digit DP problem.\n\nA few words on digit DP for those who are not so familiar with the concept. The basic idea here is to group the sequence
This is a standard digit DP problem.\n\nA few words on digit DP for those who are not so familiar with the concept. The basic idea here is to group the sequences into subsets or sub-problems, then apply regular top-down DP on each sub-problem. Here by "sequences" I just mean any integer within the range `[1,n]` , so there are `n` such sequences. They all have length (in terms of number of digits) equal to number of digits in `n`, b/c we will be including leading zeros.\n\nObviously in brute-force we can enumerate each sequence and check if it meets the condition, but this will explode in time complexity since `n` is very large. Instead we divide them into subsets. How? A very natural way is to group sequences sharing the same prefix into the same set. For instance, the two sequences `1123` and `1145` can be thought of as belonging to the same subset, since they both starts w/t the prefix `11`. Now the prefix can have different lengths, so we start with the left-most bit i.e. the most significant bit, we use a parameter `pos` to represent the current bit we are at, so `pos` equals to the length of the prefix that we have built so far. In the previous example, we can say the prefix `11` is at position `pos=2`.\n\nAn additional variable `tight`, which is boolean, is used to make it more convenient to expand the prefix; when `tight=1` it means the prefix so far exactly matchs the prefix part in `n`, therefore at `pos+1` the digit we can choose are limited to the corresponding digit in `n`. For instance if `n=12345` and we are currently at `pos=3` with `tight=1`, this would indicate the prefix we have built so far is `123`, for the next position, we cannot choose any digit larger than `4`, because if we choose say `1235` then it would have already be out-of-bounds. When `tight=0` we can choose any digit from 0 to 9. \n\nThese two variables `pos` and `tight` are standard for any digit DP solution, please refer to better tutorials e.g. [this one](https://codeforces.com/blog/entry/53960) for more detailed explanations. With `pos` and `tight` we are able to build the complete search tree from left to right in a very standard DFS framework e.g.:\n\n```\nint dfs (int pos, int tight, ...) {\n\t// return leaf node\n\t// memoization\n\t\n\tint res = 0;\n\tint limit = tight==1 ? nums[pos] : 9;\n\tfor (int i = 0; i <= limit; ++i) {\n\t\t// do sth.\n\t\tres += dfs(pos+1, newTight, ...);\n\t}\n\t\n\treturn dp[pos][tight][...] = res;\n}\n```\n\nHere for each node at position = `pos`, we just enumerate all possible digits from 0~9 or from 0 ~ `limit` depending on the `tight` condition. The digit `i` is put into position `pos+1` to expand the prefix and it is hence a child node of the current node. To return the solution of the sub-problem associated with the current node, we just accumulate from the solutions over all of its child sub-trees. This is therefore very standard top-down DP approach.\n\nA node in the tree is therefore identifiable by its prefix sequence. But in this way each node is distinct, and there are way too many nodes for memoization to work properly. Therefore we need to apply a further grouping on the prefixes. We define a mapping function `f(p)->state` where `p` is a prefix and `state` is an integer value of limited range. For instance, for LC#233 counting the digit 1 in integers, we can let `state` = number of 1\'s in the prefix.\n\nHere for this problem, notice that if we have two prefixes e.g. `22345***` and `23524***`, they are similar in the sense that they both contain two 2\'s i.e. they both have repeated digits; moreover, they both have used the same digits `2,3,4,5`, although in different ordering. So these two prefixes (and all the descendant full sequences containing these prefixes) should be grouped into the same sub-problem.\n\nConcretely, we actually need to use a 2d state variable, `(rep, mask)`. Here `rep` is a boolean value indicating whether there has already been at least one repeated digit in the prefix built so far, and `mask` is a bit-mask indicating which digits have been used in the prefix. For the previous example the state for the two prefixes should be `rep=1` and `mask=0000111100` indicating the usage of digits `2,3,4,5`. Thefore, the mapping function from prefixes to states are many-to-one, each state now identifies a sub-problem containing many sequences which share similar prefixes. It should be noted that the mapping must be chosen in such a way as to ensure the sub-problems won\'t overlap. Now we apply memoization on these sub-problems, since the number of these states will be limited, and these values will be shared and re-used throughout the DFS on the search tree.\n\nIn summary, the sub-problem (i.e. a specific subset of sequences grouped together) in digit DP is indexed by a set of variables `(pos, tight, state)`. The `dp[pos][tight][state]` value function therefore stores the solution to the corresponding sub-problem, i.e. the original problem but on the sub-set of sequences. When considering the state transitions, since `pos` and `tight` are used just for building the search tree, their transitions are always the same for different problems; in particular:\n```\nint new_pos = pos+1;\nint new_tight = (tight == 1 && i == limit ) ? 1 : 0;\n```\nHere we always transition into the child nodes by `pos+1` and compute the correct `tight` variable. The problem-specific aspect lies with the `state` variable and its transitions. Here in this problem, using `(rep, mask)` as the state, the digit DP solution is as follows in C++:\n\n```\nclass Solution {\n    vector<int> nums;\n    int s;\n    // dp[pos][tight][rep][mask]\n\t// if rep=1 means the prefix sequence contains at least one repeated digit\n    int dp[10][2][2][1024];\npublic:\n    int dfs(int pos, int tight, int rep, int mask) {\n\t\t// at leaf node exclude the cases where mask==0 i.e. leading zeros\n\t\t// if rep=1 means a sequence with at least one repeated digit has been found, so return 1;\n        if (pos == s)\n            return ( mask != 0 && rep ) ? 1 : 0;\n        \n\t\t// memoization\n        if (dp[pos][tight][rep][mask] != -1)\n            return dp[pos][tight][rep][mask];\n        \n        int limit = tight == 1 ? nums[pos] : 9;\n        int res = 0;\n        for (int i = 0; i <= limit; ++i) {\n            int newTight = (tight == 1 && i == limit) ? 1 : 0;\n\t\t\t\n\t\t\t// if mask==0 means it\'s all leading zeros, so when i=0 it\'s still leading zero, not counted;\n\t\t\t// otherwise set the corresponding bit of i to 1 in newMask\n            int newMask = (mask == 0 && i == 0) ? mask : mask | 1 << i;\n\t\t\t\n\t\t\t// exclude cases of leading zero here as well\n\t\t\t// for other cases, if rep==1 means there has already been repeated digits, so newRep = 1 also\n\t\t\t// otherwise, check if i has been set in `mask` by the bitwise AND operation; if so, newRep = 1;\n            int newRep = (mask == 0 && i == 0) ? 0 : rep | bool(mask & 1 << i);\n            \n            res += dfs(pos+1, newTight, newRep, newMask);\n        }\n        \n        return dp[pos][tight][rep][mask] = res;\n    }\n    \n    int numDupDigitsAtMostN(int n) {\n        while (n > 0) {\n            nums.push_back(n % 10);\n            n = n / 10;\n        }\n        s = nums.size();\n        reverse(nums.begin(), nums.end());\n        memset(dp, -1, sizeof(dp));\n\t\t\n\t\t// the original full problem is represented by an empty prefix\n\t\t// so pos=0\n\t\t// tight=1 b/c the first digit we place in the prefix must be bounded by nums[0] i.e. the msb in n, so it\'s tight condition is set.\n\t\t// rep=0 and mask=0 b/c in empty prefix there is no repetion, no digit used\n        return dfs(0, 1, 0, 0);\n    }\n};\n```
[]