Dynamic Programming21 sections · 916 units
Open in Course

Count Stepping Numbers - Problem Statement

Adjacent digit constraint

A stepping number has adjacent digits differing by exactly 1. Count stepping numbers in [L,R][L, R]. State: (pos,tight,lastDigit,started)(pos, tight, lastDigit, started).

Transition: if newDigitlastDigit=1|newDigit - lastDigit| = 1, valid. Handle leading zeros: before placing the first non-zero digit, any digit is valid. Track startedstarted flag. Examples: 123, 321, 12321 are stepping. 135135, 100100, 122122 are not. The stepping constraint only involves adjacent digits. Track the last digit placed to check the constraint.