The General Pattern

Most digit DP problems use this state: $dp(pos, tight, started, ...extra)$ $pos$: current digit position (0 to length-1, left to right). $tight$: are we still bounded by $N$? $started$: have we placed a non-zero digit yet? $extra$: problem-specific state (used digits, digit sum, remainder, etc.).

To compute dp, try each valid digit at $pos$, updates the state, and recurses. Base case: when $pos$ equals the length, return $1$ if valid, $0$ otherwise.