ABC154-E (digit DP) in Python

problem

Understand and show ABC154-E!

Total number

First, the total number of numbers less than or equal to N is calculated using the digit DP. Consider 314159. For example, if you have decided up to 313, any number below that is allowed. On the other hand, if the rule is 314, only 0 or 1 is allowed under one. In other words, it is necessary to have information on which digit to decide and whether less than N is decided by the decision method. ** dp [i] [j]: Determine up to the i-th digit, j = 1 if less than N is confirmed, j = 0 ** if it matches N To be determined. Since the initial value matches N at this point using up to the 0th digit dp[0][0] = 1 And. After that, the number of digits is increased, but for the next digit, the number that matches N is always 1 (same as the previous one), and the number less than N is 0 for the one that is confirmed to be less than N one before. The recurrence formula is as follows because it is the product of ~ 9 multiplied by 10 and the one equal to the previous N multiplied by 0 ~ the number of digits-1. dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0] * int(str(N)[i - 1])

code

N = input()
m = len(N)
dp = [[0] * 2 for _ in range(m + 1)]
dp[0][0] = 1

for i in range(1, m + 1):
    dp[i][0] = dp[i - 1][0]
    dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0] * int(N[i - 1])

ans = dp[m][0] + dp[m][1]

print(ans)

Total number of N or less, including K non-zero numbers

** dp [i] [j] [k]: Added condition to include k non-zero numbers ** Let l be the number in the i-th digit dp[i][0][k] = dp[i - 1][0][k] * (l == 0),dp[i - 1][0][k - 1] * (l != 0) dp[i][1][k] = dp[i - 1][1][k] + dp[i - 1][1][k - 1] * 9 + dp[i - 1][0][k] * 1 * (l != 0) + dp[i - 1][0][k - 1] * (l - 1) * (l != 0) I think it will be, but please tell me because it seems to be wasteful> <

Way of thinking

dp [i] [0] [k]: If l is 0, then k remains the same to match the given number, so dp [i -1] [0] [k], otherwise Sometimes the non-zero number increases by one, so dp [i -1] [0] [k -1].

dp [i] [1] [k]: First, one from dp [i -1] [1] [k] whose next digit is not 0, dp [i -1] [1] [k -1] The next digit is 9 from 1 to 9. Next, if l is not 0, dp [i -1] [0] [k] with the next digit as 0 becomes dp [i -1] with the next digit as 1 ~ (l -1). ] [0] [k -1] transitions by l -1. (Difficult to understand cedar)

code

N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

print(dp[m][0][K] + dp[m][1][K])

Afterword

Please give me some advice. .. .. .. I will answer as many questions as I can. .. .. ..

References

Introduction to Digit DP