Daily LeetCode – day0081 0902. Numbers At Most N Given Digit Set

// 0902. Numbers At Most N Given Digit Set
class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        int quantity = digits.length;
        char[] digitsArray = new char[quantity];
        for (int i = 0; i < quantity; ++i) {
            digitsArray[i] = digits[i].charAt(0);
        }
        char[] nArray = String.valueOf(n).toCharArray();
        int len = nArray.length;
        int[] memory = new int[len];
        memory[0] = 1;
        for (int i = 1; i < len; ++i) {
            memory[i] = memory[i - 1] * quantity;
        }
        int ans = 0;
        for (int i = 1; i < len; ++i) {
            ans += memory[i];
        }
        ans += dfs(0, digitsArray, quantity, nArray, len, memory);
        return ans;
    }

    private int dfs(int currentIndex, char[] digitsArray, int quantity, char[] nArray, int len, int[] memory) {
        if (currentIndex == len) return 1;
        int ret = 0;
        for (int i = 0; i < quantity; ++i) {
            if (digitsArray[i] < nArray[currentIndex]) {
                ret += memory[len - 1 - currentIndex];
            } else if (digitsArray[i] == nArray[currentIndex]) {
                ret += dfs(currentIndex + 1, digitsArray, quantity, nArray, len, memory);
            }
        }
        return ret;
    }
}

学习笔记：
今天这是一道困难题，所以做到了大半夜1:40才做完。
可以用数位DP，数学算法，记忆化搜索。
我很久没写记忆化搜索了，就写了记忆化搜索的。
主要是分类讨论，首先是位数少于n的，那就直接排列就行了。
1位的全排列、2位的全排列、3位的全排列，然后加起来。

位数相同的话，就要开始深搜了。
先从第0位开始看，我们的材料比n的第0位小，那就说明后面可以随便排列。
ret += memory[len - 1 - currentIndex];
我们的材料比n的第0位大，
那就说明，后面怎么排列都没用了。
我们的材料比n的第0位相等，那就得看后面的排列了，变成了原问题的子问题。
ret += dfs(currentIndex + 1, digitsArray, quantity, nArray, len, memory);

最后要注意一点，如果最后的一位相等，那再进入深搜的时候，就会触发base case，我一开始的base case写错了，返回了0，应该返回的是1。
if (currentIndex == len) return 1;
为什么是1呢，我们要想一下，最后一位相等了，那说明这个数字是等于n的，题目要求就是小于等于n，之前过程中我们也没加过这个1，所以这里我们需要加1。