Consecutive Ones - Walkthrough

Count binary numbers $\leq 101$ (5 in decimal) with no consecutive 1s. Track the previous digit. N = 101 in binary. Position $0$: try $0$ (loose) or 1 (tight).

If $1$, prevDigit = 1. Position $1$: if prev = 1 and tight, can only try $0$ (since 1 would make consecutive 1s). If loose, try both but skip 1 if prev = 1. Position $2$: continue. Valid numbers: $000$, $001$, $010$, 100, 101. That's 5 numbers. The DP counts all valid paths.