Digit DP

Count (or optimise over) numbers in a range $[L,R]$ satisfying a digit-wise property. The technique: build the number digit by digit, tracking just enough state.

The standard state

dp[pos][tight][started][... problem-specific ...]

Component	Meaning
pos	which digit position we are filling (most significant first)
tight	are all previous digits equal to the bound’s prefix? If so, this digit is capped
started	have we placed a non-zero digit yet? (needed to handle leading zeros correctly)
extra	sum of digits, remainder mod $k$, last digit, a mask of used digits, …

The template

string num;
int memo[20][2][2][STATES];
bool done[20][2][2][STATES];
 
long long go(int pos, bool tight, bool started, int state) {
    if (pos == (int)num.size()) return started && accept(state);
    if (done[pos][tight][started][state]) return memo[pos][tight][started][state];
    done[pos][tight][started][state] = true;
 
    int hi = tight ? num[pos] - '0' : 9;
    long long res = 0;
    for (int d = 0; d <= hi; d++) {
        bool nStarted = started || d > 0;
        int nState = nStarted ? transition(state, d) : state;
        res += go(pos + 1, tight && (d == hi), nStarted, nState);
    }
    return memo[pos][tight][started][state] = res;
}
 
long long countUpTo(long long x) {
    if (x < 0) return 0;
    num = to_string(x);
    memset(done, 0, sizeof done);
    return go(0, true, false, INITIAL);
}
 
long long countRange(long long L, long long R) {
    return countUpTo(R) - countUpTo(L - 1);
}

Answering $[L,R]$ as $f(R)-f(L-1)$ is standard — never try to bound both ends at once.

The two flags, explained

tight. While every digit so far matches the bound’s prefix, the current digit cannot exceed the bound’s digit. Once you place something smaller, all later positions are free (tight becomes false and stays false). This is why tight only ever turns off.

started. Leading zeros are not real digits. Without this flag, 007 would be counted as having digit sum 7 and three digits, and problems like “no two equal adjacent digits” would wrongly reject numbers starting with 0. Only turn on state tracking once a non-zero digit has appeared.

The most common bug

Forgetting started when the property involves the digits themselves (digit count, distinct digits, adjacent digits). Symptom: off-by-a-few answers on small ranges, correct on large ones.

Typical extra state

Property	State
Digit sum equals $S$	current sum, $O(9\cdot 18)$ values
Divisible by $k$	remainder mod $k$
No two adjacent equal digits	previous digit
Digits non-decreasing	previous digit
Contains digit 7 / avoids “13”	a small flag or automaton state
All digits distinct	a 10-bit mask
Divisible by its digit sum	(digit sum, remainder mod each candidate sum) — loop over the target sum
Palindromic	build from both ends, or fix the first half
At most $k$ non-zero digits	a counter

Beyond counting

The same skeleton computes sums and minima over the qualifying numbers — return a pair (count, sum) and combine accordingly:

pair<long long,long long> go(...) {          // {count, sum of numbers}
    ...
    auto [c, s] = go(pos + 1, ...);
    cnt += c;
    sum += s + (long long)d * pow10[len - pos - 1] % MOD * c;
}

Non-decimal bases

Nothing is decimal-specific. Replace 9 with base - 1 and to_string with a base conversion. Binary digit DP is common for problems about XOR or bit constraints, and it often composes with a binary trie view of the same problem.

Complexity

$O(\text{digits}\times 2\times 2\times \text{states}\times \text{base})$. With 18 decimal digits and a few thousand extra states this is trivially fast — digit DP is almost never the bottleneck once the state is right.

Recognising it

The giveaway is a huge range ($10^{18}$) combined with a property that depends only on the digits. Any time you would want to loop from $L$ to $R$ and cannot, digit DP is the first thing to try.

See also: Designing States · Memoization · Number Theory