Counting by construction
Digit DP counts numbers up to a bound that satisfy some property of their digits, such as having a limited digit sum or no repeated digits. Instead of checking each number, you build numbers digit by digit from the most significant position.
The tight flag
The key extra state is a tight flag that records whether the prefix built so far equals the bound's prefix:
- If tight is true, the next digit may not exceed the bound's digit at this position.
- If tight is false, the next digit may be anything from zero to nine.
Other state carries the property being tracked, for example the running digit sum or the previous digit. A leading zero flag often handles numbers with fewer digits.
Combining the pieces
The state is roughly the position, the tight flag, and the tracked property. Memoizing across positions when not tight reuses work, since many prefixes lead to the same free counting subproblem.
Key idea
Digit DP builds numbers position by position, tracking a tight flag against the bound plus the digit property, so counts over a whole range reduce to a small memoized search.