class Solution {

    public int numDupDigitsAtMostN(int n) {

        nums = String.valueOf(n).toCharArray();

        memo = new int[nums.length][1 << 10];

        for (int i = 0; i < nums.length; i++) {

            Arrays.fill(memo[i], -1);

        }

        return n - dfs(0, 0, true, false);

    }

    char[] nums;

    int[][] memo;

    /**

     * @param i     当前位

     * @param mask  前面选过的数字集合，0 ~ 9, 一共 10 位

     * @param limit 是否收到了 n 的约束

     * @param isNum i 前面的数位是否填了数字

     *              例如 : 010, 不能有前导 0, 若 i 前面没有任何数字，当前 i 位要么跳过，要么至少从 1 开始填

     * @return 统计不重复的数字个数

     */

    public int dfs(int i, int mask, boolean limit, boolean isNum) {

        if (i == nums.length) {

            return isNum ? 1 : 0;

        }

        // 受到限制或者前面没有数字，只有一种情况，没有必要记忆化

        // 例如 : 3 2 8

        //        3 2 i, 当前位 i 只能由 3, 2 由来只有一种情况

        // if (memo[i][mask] != -1) {

        //      这样是不行的

        //      3 2 8 

        //      2 1 i | 1 2 i

        if (!limit && isNum && memo[i][mask] != -1) {

            return memo[i][mask];

        }

        // 当前可以选择的最大值

        // 例如 : 2 9 8

        //           i , i - 1 选择了 9, 当前最高只能选择 8

        int up = limit ? nums[i] - '0' : 9;

        int ans = 0;

        // 只有前面没有任何数字，当前位数可以跳过，可以不跳过

        // 前面有数字，当前位不能跳过，若跳过当前位，会导致重复

        //  例如 : 2 3 3  （t 表示跳过）

        //        t 2 1

        //        2 t 1 | 2 1 t

        // 只有前面没有数字，才可以跳过，且保证不重复

        if (!isNum) {

            // 跳过当前数字可以随便选，没有限制

            ans = dfs(i + 1, mask, false, isNum);

        }

        // 防止前导零

        //  例如 : 010, 不能有前导 0, 若 i 前面没有任何数字，当前 i 位要么跳过，要么至少从 1 开始填

        int d = isNum ? 0 : 1;

        for (; d <= up; d++) {

            // 没有被使用过

            if ((mask >> d & 1) == 0) {

                ans += dfs(i + 1, mask | (1 << d), limit && d == up, true);

            }

        }

        if (!limit && isNum) {

            memo[i][mask] = ans;

        }

        return ans;

    }

}