Chapter 8: Digit DP

How many numbers between 1 and 987,654,321 have a digit sum divisible by 7? Have no repeated digits? Contain the substring 42? Brute force is impossible at that scale. Digit DP processes numbers digit by digit from most significant to least, counting valid completions without enumerating every integer.

The technique applies to counting and optimization problems on ranges [0, N] or [L, R] with constraints on digits. Range queries decompose as count(R) − count(L − 1).

The Tight Constraint

This is the central insight of digit DP. As you build a number from left to right, track whether your prefix still matches the upper bound N exactly:

tight = true: all previous digits matched N's digits. The current digit is bounded by N[pos] — you cannot exceed it.
tight = false: some previous digit was strictly smaller than N's. You are free to place any digit 0–9 from here on.

N = 5432

At pos=0, tight=true:  d can be 0..5
  If d=5: next tight=true  (still matching prefix "5")
  If d=3: next tight=false (prefix "3" < "5", now free)

At pos=1 with prefix "5" (tight=true): d can be 0..4
At pos=1 with prefix "3" (tight=false): d can be 0..9

This single flag encodes the upper bound without iterating to N.

Digit DP is always recursive memoization — the tight flag makes bottom-up tabulation awkward because the digit limit at each cell depends on the path taken. Top-down DFS with memoization is the natural and standard implementation.

Count Special Numbers

LeetCode 357 (adapted): Count numbers in [1, N] where all digits are distinct. State:

dp(pos, mask, tight, started)

  pos     — current digit position (0-indexed from left)
  mask    — bitmask of digits already used (bits 0..9)
  tight   — are we still bounded by N's prefix?
  started — have we placed a non-leading-zero digit yet?

What does dp(pos, mask, tight, started) represent in Count Special Numbers?

At each position, try every valid digit d from 0 to the tight limit. Skip digits already in mask (once the number has started). Leading zeros do not count as using digit 0 — the started flag handles this.

Reusable Digit DP Template

Most digit DP problems share the same skeleton. Adapt three things: the state (extra parameters like mod or mask), the validity check for each digit, and the base case return value (count 0/1 or min/max).

function dp(pos, state, tight, started):
    if pos == len(N): return baseCase(started, state)
    if memoized: return cached

    limit = tight ? N[pos] : 9
    ans = 0
    for d in 0..limit:
        if not valid(pos, d, state, started): continue
        ans += dp(pos+1, nextState, tight && d==limit, started || d>0)
    return ans

Don't forget the started flag for problems with leading zeros. Without it, numbers like 005 and 5 are double-counted or mishandled, and single-digit edge cases break. Also remember that count(L, R) = count(R) − count(L − 1) — the lower bound needs careful off-by-one handling.

Summary

When: counting or optimizing over numbers in a range with digit constraints
State: position + problem-specific state + tight + started
Key insight: tight encodes the upper bound
Implementation: recursive memoization (top-down)
Range trick: f(L, R) = f(R) − f(L − 1)

Digit DP problems often look like math puzzles (“count numbers where…”). The giveaway is a huge range (N up to 10¹⁸) with per-digit constraints. If you find yourself trying to iterate every number, switch to digit-by-digit counting.