Digit DP
Count numbers in a range with a digit property by processing digits with a "tight" flag.
Digit DP: Numbers up to 275 without a 7
Position 2, tight: 275 has the digit 5 here. A digit below 5 frees the rest: 5 allowed choices x 1 = 5. Choosing 5 itself keeps the number tight, adding the tight count of the next position, 1. Total 6.
Cost
- Best
- O(digits * states)
- Average
- O(digits * states)
- Worst
- O(digits * states)
- Space
- O(digits * states)