DPDynamic Programming
Digit DP (counting with prefix state)
Count numbers in [0, N] with a digit property by scanning N's digits with a "tight" flag and a small property state.
2
0
5
1
0
2
| tight · unstarted | tight · started | free · unstarted | free · started | |
|---|---|---|---|---|
| before digit 0 | 1 | 0 | 0 | 0 |
| after 1 digit | · | · | · | · |
| after 2 digits | · | · | · | · |
| all 3 digits placed | · | · | · | · |
what each state means about the prefix
tight · unstarted — nothing placed yet; still exactly N's prefixtight · started — prefix equals (empty), so digit 0 is capped at 2free · unstarted — only leading zeros so far, and already below Nfree · started — strictly below N's prefix; digit 0 may be anything but 0
digits of N
| pos | digit | status |
|---|---|---|
| 0 | 2 | choosing |
| 1 | 5 | later |
| 2 | 0 | later |
1/22Count the integers in [1, 250] whose decimal form contains no digit 0. Enumerating them one by one is O(N); instead we build the number one digit at a time and count whole families of numbers at once. That only works if a prefix can be summarised by a small state, and the whole difficulty is choosing it.
Initial state (empty prefix)Source state being spreadDestination cell being incrementedSettled countsCells that make up the answer
PseudocodeLearn Digit DP →
1D = decimal digits of N; L = len(D)2cnt[0][tight=1][started=0] = 1 # the empty prefix still matches N3for pos in 0 .. L-1:4 for each state (tight, started) with cnt > 0:5 hi = tight ? D[pos] : 9 # tight is what caps the alphabet6 for d in 0 .. hi:7 if started and d == 0: continue # a real 0 digit is forbidden8 cnt[pos+1][tight and d == D[pos]][started or d > 0] += cnt[pos][tight][started]9answer = cnt[L][tight=1][started=1] + cnt[L][tight=0][started=1]Variables
N250
digits2 5 0
L3
Complexity
worst O(D × S × B) — D digits (≤ 19), S property states, B base (10)
space O(D × S)
Speed