The Forbidden Pair

**Scenario.** Count binary strings of length n with no two consecutive 1s. Direct construction looks messy. What is the cleanest model? **Which approach is the best fit? The program only needs to print the letter.** **A)** Enumerate all 2^n strings and filter — n is small anyway **B)** A DP over positions whose state is 'did the previous position hold a 1?' — the adjacency condition decomposes to one bit **C)** A number-theoretic formula based on n mod something **D)** Sort the strings and remove conflicts pairwise