AlgoScope

Digit DP

Count numbers in a range with a digit property by processing digits with a "tight" flag.

Dynamic programming, technique, expert
Tight at position 2: 6.pos 0pos 1pos 2endtightfree6191
Tight at position 2: 6.pos 0pos 1pos 2endtightfree6191

Digit DP: Numbers up to 275 without a 7

Decision, step 3 of 8

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)