Leetcode数位DP总结

[ZhangCheng-zh]

数位DP总结

详解和题单

class Solution {
    char[] s;
    int l;
    int[] dp;
    String[] digits;
    public int atMostNGivenDigitSet(String[] digits, int n) {
        s = Integer.toString(n).toCharArray();
        l = s.length;
        this.digits = digits;
        dp = new int[l];
        Arrays.fill(dp, -1);
        return dfs(0, true, false);
    }
    
    int dfs(int i, boolean hasLimit, boolean hasDigit) {
        if (i == l) return hasDigit ? 1 : 0;
        if (!hasLimit && hasDigit && dp[i] >= 0) return dp[i];
        int res = 0;
        if (!hasDigit) res = dfs(i + 1, false, false);

        int ceil = hasLimit ? (s[i] - '0') : 9;
        for (var d: digits) {
            if ((d.charAt(0) - '0') > ceil) break;
            res += dfs(i + 1, hasLimit && (d.charAt(0) - '0' == ceil), true);
        }
        if (!hasLimit && hasDigit) dp[i] = res;
        return res;
    }
}

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        s = str(n)
        @cache
        def f(i: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s): return int(is_num)  # 如果填了数字，则为 1 种合法方案
            res = 0
            if not is_num:  # 前面不填数字，那么可以跳过当前数位，也不填数字
                # is_limit 改为 False，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束
                # is_num 仍然为 False，因为没有填任何数字
                res = f(i + 1, False, False)
            up = s[i] if is_limit else '9'  # 根据是否受到约束，决定可以填的数字的上限
            # 注意：对于一般的题目而言，如果此时 is_num 为 False，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况
            for d in digits:  # 枚举要填入的数字 d
                if d > up: break  # d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环
                # is_limit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束
                # is_num 为 True，因为填了数字
                res += f(i + 1, is_limit and d == up, True)
            return res
        return f(0, True, False)