Counting over a numeric range
Some problems ask how many numbers up to a bound satisfy a property, such as having a limited digit sum or avoiding a forbidden digit. The range can be astronomically large, so you cannot test each number. Digit dynamic programming builds numbers one digit at a time and counts valid completions.
The tight flag
The central idea is a flag called tight. While you are still matching the upper bound's leading digits exactly, the next digit is capped by the bound's digit at that position. Once you place a smaller digit than the bound allows, you become free and every later digit may range over all allowed values.
- Process digits from most significant to least.
- Track the position, whatever running property you care about, and the tight flag.
- When tight, the digit upper limit is the bound's digit. When free, it is the maximum digit.
Memoizing the free states
When you are no longer tight, the count of valid completions depends only on the position and the property, not on the exact prefix. Those states repeat, so you cache them. The tight states form a single thin path and are not cached.
Key idea
Build numbers digit by digit, carry a tight flag that bounds each digit against the limit, and memoize the free states whose completion counts repeat.