Digit DP
A position-by-position DP over the decimal expansion of an upper bound, with tight and leading-zero states.
Digit DP
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Digit DP is the standard way to count or optimize over huge numeric ranges when the property depends on the decimal digits themselves. The main shift is to stop thinking about numbers as integers and start thinking about them as left-to-right digit constructions under an upper-bound constraint.
Problem-Driven Motivation
Suppose \(R\) can be as large as \(10^{18}\), and we must count numbers in \([L,R]\) whose digits satisfy some rule:
no adjacent equal digits,
digit sum equals \(S\),
remainder modulo \(m\) is fixed,
the decimal expansion avoids some forbidden pattern.
Brute force is impossible. The only thing that makes the problem manageable is that while building a number from left to right, the future only depends on a small amount of state about the prefix.
Recognition Pattern
Digit DP is the right tool when:
the numeric bound is enormous,
the validity condition is defined on digits,
the natural range answer is \(\texttt{solve}(R) - \texttt{solve}(L-1)\),
the important memory about the prefix is small enough to memoize.
If the property is not about digits at all, forcing a digit-DP model usually makes the problem worse.
Derivation
Write the upper bound \(N\) as a digit string. Process it from most significant digit to least significant digit.
The standard state has three conceptual parts:
position: which digit are we choosing,
tight: whether the built prefix is still exactly equal to the prefix of \(N\),
problem state: whatever information about the chosen digits still matters.
The
tightflag is what enforces the upper bound. While it is true, the next digit cannot exceed the corresponding digit of \(N\). Once it becomes false, the remaining digits are unconstrained.Leading zeros need special care. In many problems, ``we have not started the number yet'' must be represented explicitly, or folded into a sentinel previous digit.
Worked Problem
Problem.
Count integers in \([L,R]\) whose decimal representation has no two adjacent equal digits.
Why naive fails.
The interval can be enormous, so scanning every number is impossible.
State design.
Process digits left to right and keep:
pos,tight,prev= previous chosen digit, or a sentinel \(10\) meaning ``no real digit has started yet''.
Transition.
At each position choose the next digit \(d\) between \(0\) and the current limit. The transition is illegal only if:
the number has already started,
and \(d = prev\).
If the number has not started and we place another leading zero, the sentinel \(10\) stays.
Why memoization works.
When tight = false, the future depends only on \((pos, prev)\). Two states with the same values have identical continuations, so they can share one memoized answer.
Implementation Reasoning
The important implementation habit is to write \(\texttt{solve}(N)\) first and keep range logic separate: \[ answer(L,R) = solve(R) - solve(L-1). \]
For the no-adjacent-equal example, the sentinel previous digit removes the need for a separate started flag. That is often cleaner than carrying two booleans.
The code below is a reusable digit-DP skeleton for this style of problem:
digits are processed left to right,
memoization is used only for non-tight states,
one extra state parameter (
prev) captures the property.
Correctness Intuition
Every valid number in \([0,N]\) corresponds to exactly one root-to-leaf path in the digit DP. The tight flag ensures that invalid paths exceeding \(N\) are never explored. The problem state stores exactly the information needed to judge future validity, so memoized non-tight states are genuinely identical subproblems.
Complexity Analysis
If the custom state space has size \(S\), the rough bound is \[ O(\text{digits} \cdot S \cdot 10). \]
For the no-adjacent-equal example, \(S\) is tiny: 11 possible previous-digit states.
Common Pitfalls
Memoizing tight states even though they depend on the exact upper-bound prefix.
Mishandling leading zeros and accidentally treating them as real digits.
Forgetting the \(\texttt{solve}(R) - \texttt{solve}(L-1)\) pattern.
Letting the custom state explode until the DP is no longer small.
Variants and Failure Modes
Replace
prevby digit sum, remainder modulo \(m\), bitmask of used digits, or automaton state.More complicated properties may need both
startedand a custom state.If the property depends on the number in a non-digit way, digit DP is the wrong abstraction.
Practice Problems
Count numbers with no adjacent equal digits.
Count numbers with digit sum or remainder restrictions.
Count numbers avoiding a forbidden decimal substring.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct DigitDpNoAdjacent {
string digits;
long long memo[20][11];
bool seen[20][11];
long long dfs(int pos, int prev, bool tight) {
if (pos == (int)digits.size()) return 1;
if (!tight && seen[pos][prev]) return memo[pos][prev];
int limit = tight ? digits[pos] - '0' : 9;
long long answer = 0;
for (int digit = 0; digit <= limit; ++digit) {
int next_prev = prev;
if (prev == 10 && digit == 0) {
next_prev = 10; // still only leading zeros
} else {
if (digit == prev) continue;
next_prev = digit;
}
answer += dfs(pos + 1, next_prev, tight && digit == limit);
}
if (!tight) {
seen[pos][prev] = true;
memo[pos][prev] = answer;
}
return answer;
}
long long count_up_to(long long limit) {
if (limit < 0) return 0;
digits = to_string(limit);
memset(seen, 0, sizeof(seen));
return dfs(0, 10, true);
}
long long count_in_range(long long left, long long right) {
return count_up_to(right) - count_up_to(left - 1);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.