[Python3] Digit DP + BIT Mask - Simple + Detail Explanation - Easy To Understand
Intuition\nFind total of numbers in range with specific condition => digit DP\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. In
# Intuition\nFind total of numbers in range with specific condition => digit DP\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Initialization\n- The input number `n` is converted to a list of digits (`digits`).\n2. Dynamic Programming Function\n- The function `dp` is a recursive dynamic programming function that calculates the count of numbers with repeated digits.\n- Parameters:\n    - `pos`: The current position (digit position).\n    - `mask`: A bitmask representing the used digits.\n    - `is_smaller`: A boolean indicating whether the current number is smaller than `n`.\n- Base Case:\n    - If `pos` reaches the length of `digits`, return 1, indicating a valid number with repeated digits.\n- Recursive Case:\n    - Iterate over the possible digits (`d`) from 0 to the upper limit based on `is_smaller`.\n    - Check if the digit `d` is already used (`mask & (1 << d)`). If used, skip to the next digit.\n    - Update `new_is_smaller` based on whether the current digit is smaller than the upper limit.\n    - Update `new_mask` to include the current digit (`d`) in the bitmask.\n    - Recursively call `dp` for the next position (`pos + 1`) with the updated parameters.\n    - Accumulate the total count of valid numbers.\n3. Main Fuanction\n\n- Call the `dp` function with initial parameters (`pos=0, mask=0, is_smaller=True`).\n- Subtract 1 from the result to exclude the number `0`.\n- Return the result as the count of numbers with repeated digits up to `n`.\n\n4. Note\nThe solution employs dynamic programming to count the numbers with repeated digits by recursively considering each digit\'s possibilities. The cache decorator is used for memoization, which helps avoid redundant calculations and improves the efficiency of the solution. Finally, the main function returns the total count of such numbers in the given range.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def numDupDigitsAtMostN(self, n: int) -> int:\n        digits = list(map(int, str(n)))\n        \n        @cache\n        def dp(pos: int, mask: int, is_smaller: bool = True) -> int:\n            if pos == len(digits): return 1\n\n            total = 0\n            upper_limit = digits[pos] if is_smaller else 9\n            for d in range(upper_limit + 1):\n                if mask & (1 << d): continue\n                new_is_smaller = is_smaller and d == upper_limit\n                new_mask = mask if mask == 0 and d == 0 else mask | (1 << d)\n                total += dp(pos + 1, new_mask, new_is_smaller)\n\n            return total\n\n        return n - (dp(0, 0) - 1)\n```
['Dynamic Programming', 'Bitmask', 'Python3']