Explanation for Provided Solution using Dynamic Programming?

Tags: #<Tag:0x00007f2427ad7738>


I solved this question using recursion.

I am not able to get the approach or solution provided in editorial and also could not find any reference anywhere.
I was able to understand what the solution is doing by reading Java Editorial solution.
Can someone help me better understand the dynamic programming approach on why or how it is able to work.


Finally I was able to implement the solution approach. But weirdly enough solution approach != given solutions.

            # case 3: B == len(C)
            # numbers lower than digit d
            lower = [0]*10
            j = 0
            for i in range(10):
                lower[i] = lower[i-1] 
                if j < len(A) and A[j] == i:
                    lower[i] += 1
                    j += 1
            for a in A: lower[a] -= 1 # above count counts less-equal
            # dp(i) = count taking first i digits of C
            # dp(i-1) always less than C(:i-1), so all d possible
            # if we have seen equal numbers up to C(:i-1) 
            # then additional lower[i] possible including C(:i-1)
            d = len(A)
            dp = [0] * (B+1)
            C = [int(c) for c in str(C)]
            equal = True # seen equal numbers so far 
            for i in range(1, B+1):
                dp[i] = dp[i-1] * d # dp[i-1] is always lower by construction
                if equal: # have seen equal digits upto previsou step
                    dp[i] += lower[C[i-1]]
                    equal = C[i-1] in A # this digit equal as well or not?
                if i == 1 and B != 1 and A[0] == 0: # don't include 0 if length == 1
                    dp[i] -= 1
            return dp[-1]


Thank you for sharing your code here (and the comments!). There’s a DP approach in the Python3 Lightweight solution.