力扣 902. 最大为N的数字组合

数位dp

def atMostNGivenDigitSet(digits, n):
    n_s = str(n)
    m, k = len(digits), len(n_s)
    dp = [[0, 0] for _ in range(k + 1)]
    dp[0][1] = 1
    for i in range(1, k + 1):
        for d in digits:
            if d == n_s[i - 1]:
                dp[i][1] = dp[i - 1][1]
            elif d < n_s[i - 1]:
                dp[i][0] += dp[i - 1][1]
            else:
                break
        if i > 1:
            dp[i][0] += m + dp[i - 1][0] * m
    return sum(dp[k])