Digit DP: counting numbers with a property

"How many integers in [L, R] have digit sum divisible by 7?" or "...contain no two equal adjacent digits?" or "...never contain the substring 49?" When R can be 10¹⁸, enumeration is hopeless — there are a quintillion candidates. Digit DP counts them without listing them, by building the number one digit at a time, left to right, carrying only enough state to know whether the property still holds.

First, collapse the range. Define f(X) = count of valid numbers in [0, X]; then the answer over [L, R] is f(R) − f(L − 1). Now you only ever count up to a bound, which is the case the DP knows how to handle.

The state is (position, tight, accumulator). position is which digit you are placing. tight is the one idea that makes the whole thing work: it is true while the digits you have placed exactly match the prefix of the bound, which caps the next digit at the bound's digit; once you place anything smaller, tight goes false and every remaining digit is freely 0–9. accumulator is whatever the property needs — a running digit sum mod 7, the previous digit, a small automaton state.

Trace counting numbers ≤ 325 whose digit sum is divisible by 3. Hundreds digit ranges 0–3 (capped by 3, so tight stays true only on the branch that picks 3). On the 0, 1, 2 branches tight is already false, so the remaining two digits run 00–99 freely and you count those by the accumulator alone; only the "picked 3" branch stays tight and caps the tens digit at 2. The bound is respected without ever enumerating.

Digit DP is the answer whenever the question is "count numbers up to ~10¹⁸ satisfying a digit-local property." The recipe never changes: split the range with f(R) − f(L−1), walk the digits, keep tight plus a tiny problem-specific accumulator. Once the tight flag clicks, every such problem looks the same.