At position :
You can always place . Recurse with prev = .
You can place only if prev and (not tight or ). If prev was and you try to place , you'd create . Skip that branch. The tight logic works the same as base : if tight and , you can't place . This formula tells you how to compute dp(pos, tight, prev) from dp values at later positions. Getting this right is the core of DP.