Dynamic Programming9 min read

Digit DP

Count numbers with digit constraints — without checking each one
time:\(O(digits · 10 · extra_states)\)space:\(O(digits · extra_states)\)typical:\(O(18 · 10 · k)\) for N ≤ \(10^{18}\)

Imagine counting how many locker numbers between 1 and 10,000 have no repeated digits. Checking every number one by one would mean 10,000 comparisons. But what if N were \(10^{18}\)? Checking one number per nanosecond would take 31 years.

Digit DP solves this by building candidate numbers digit by digit, from the most significant digit down. At each position, we track just enough state to know whether the number-so-far can lead to a valid answer — and we cache the results.

The Tight Constraint

Here's the key idea. Suppose you're counting valid numbers from 0 to N = 743. You build numbers one digit at a time:

  • First digit: can be 0–7. If you choose 6 (less than 7), you're now free — the remaining digits can be anything 0–9. If you choose 7 (equal to N's digit), you're still tight — the next digit can only go up to 4.

The tight flag tracks whether every digit placed so far has exactly matched N's prefix. Once you go below N at any digit, tight becomes false and the rest can be filled freely.

Standard State Variables

pos — which digit position we're filling (0 = leftmost).

tight — are we still constrained by N's prefix? If true, the current digit can only go up to N's digit at this position.

leading_zero — have we placed a non-zero digit yet? This prevents counting "007" as having a leading zero that breaks the property we're checking.

accumulated state — whatever property we're tracking: digit sum mod k, last digit placed (to catch adjacent duplicates), count of a specific digit, etc.

The Template

The recursive function looks like: solve(pos, tight, leading_zero, ...state). At each step, determine the digit limit (tight ? N[pos] : 9), try every digit from 0 up to the limit, update the state, and recurse. Memoize results for states where tight = false — those are reusable across different prefixes.

Range Queries: Count in [L, R]

Digit DP naturally answers "how many valid numbers are in [0, N]?" For a range [L, R], use count(R) − count(L − 1). Two calls, done.

Note: Once tight becomes false, you're in free territory — the sub-problem (pos, false, leading, state) has the same answer no matter what upper bound you started with. That's why memoization only applies to non-tight states.

Count numbers in [1, N] with no two adjacent equal digits

from functools import lru_cache


def count_no_adjacent(N):
    digits = [int(d) for d in str(N)]
    n = len(digits)


    @lru_cache(maxsize=None)
    def solve(pos, tight, last_digit, leading):
        if pos == n:
            return 1  # valid number built
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            if not leading and d == last_digit:
                continue  # adjacent duplicate
            new_tight = tight and (d == limit)
            new_leading = leading and (d == 0)
            new_last = -1 if new_leading else d
            total += solve(pos + 1, new_tight, new_last, new_leading)
        return total


    return solve(0, True, -1, True)


print(count_no_adjacent(100))   # 91
print(count_no_adjacent(1000))  # 738
Output
91
738

Common Accumulated States

  • No digit 4: no extra state needed — just skip d == 4 in the loop.
  • Digit sum divisible by k: accumulate sum mod k (values 0 to k−1).
  • No adjacent equal digits: store the last digit placed (values 0–9 or −1 for leading zeros).
  • Count of a specific digit: store how many times it's appeared.

The total state space is positions × 2 (tight) × extra states. For N up to \(10^{18}\), positions ≤ 19. Most problems have tiny extra state, so the memoization table has only hundreds of entries.

Complexity

🐢 Brute forceChecking each number individually — unusable for ranges up to \(10^{18}\)
Linear in range size\(O(R − L)\)
⚡ Digit DP (time)For N ≤ \(10^{18}\): 19 positions × 10 digits × problem-specific state — often under 10,000 ops
Tiny — logarithmic in N\(O(digits · 10 · states)\)
💾 Digit DP (space)Tight states aren't cached; only non-tight states are reused
Memo table for non-tight states\(O(digits · states)\)
📐 Digit sum mod k exampleEven for k = 1000, this is only ~190,000 states — essentially instant
19 positions, k extra states\(O(19 · 10 · k)\)

Quick check

What does the 'tight' flag mean when it's true?

Continue reading

DP Pattern
Never solve the same puzzle piece twice — write it down and look it up next time
→
Bitmask DP
Track every possible subset of choices in a single integer
→