Sign in to watch this lesson
Advanced - Dynamic Programming · 4:28
Digit DP
To count the numbers in [A, B] with a digit property, we compute f(N), the count from 0 to N, by building the numbers digit by digit and answer f(B) - f(A - 1). A tight flag keeps the prefix level with N; once a digit drops below N's digit, the rest of the subtree is free and depends only on the digits left and a small summary (here the digit sum mod 7), so it is memoised once and shared, even across calls. We also handle leading zeros with a started flag and the edge cases A = 0 and 10^18.
You will learn
- Reduce a range count to f(B) - f(A - 1) and handle A = 0 (f(-1) = 0)
- Write a digit DP with the state (position, tight, started, extra), capping the next digit at N's digit while tight
- Memoise only free states, keyed by the number of digits left, so the memo is shared across calls, and estimate the work as positions × |extra| × 10
- Recognise when leading zeros change the answer (e.g. no two equal adjacent digits) and fix it with a started flag