CONCEPT · International Grandmaster
Digit DP
also digit dynamic programming
Count numbers ≤ n with a digit property by walking digits. State is (pos, tight, small flags). n=10^18 is 18 steps.
Intuition
Once you drop below n's prefix, every later digit is free. tight is that one bit of memory.
When to reach for it
- How many in [L,R] have digit sum / avoid a digit / are palindromes
- CSES Counting Numbers
- Any 10^18 counting question on digits
Usual pits
- Forgetting tight in the memo key
- Leading zeros vs 'started'
- count(R)-count(L) instead of count(L-1)
- Generating all n values