最大为N的数字组合

Leetcode Link: 902. 最大为 N 的数字组合 题解 - 力扣（LeetCode）

题目

解法一

思路： 本题需要注意的地方

1. 有没有前导 0，决定着可选数字中含不含 0。注意题解中 digits 中的范围是不含 0 的。

   如果所有情况下的可选数字中都没有0，则结果中不会出现位数比n小的结果，如n=100，则结果中不会找到99或者9这种小于3位的数字。

2. base case 中，如果全部为前导 0，则需要返回 0

   必需判定走到最后一个位置的时候是不是前面全部都是前导0，否则直接返回1是错误的，因为会算0000，而digits中是不含0的

题解：

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        s = str(n)
        # 如果有没有前导0，则待选数组里不能包括0
        digits1 = [int(x) for x in digits]
        # 如果有前导0，则待选数组里必需包括0
        digits0 = [0] + digits1.copy()
        
        @cache
        def process(i, is_bound, is_zero):
            if i == len(s):
                return not is_zero # 注意这里的返回值，写的很好
 
            maxi = int(s[i]) if is_bound else 9
 
            res = 0
            # 根据是不是前导0来决定待选的digits
            digits = digits0 if is_zero else digits1
            for val in digits:
                if val > maxi: break
                res += process(i+1, is_bound and val==maxi, is_zero and val==0)
            
            return res
        
        return process(0, True, True)

还有其他解法， 重点看的是数位dp

启发和联系