Binary Strings Without Two Ones Together
Count the binary strings of length n in which no two 1s are adjacent.
n = 3 -> 5 000 001 010 100 101
Enumerating all 2^n strings and filtering works to about n = 25 and not to
50.
A count of "strings of length i" is not enough to continue, because whether a
1 may be appended depends on the last character. So split by it:
end0[i] strings of length i ending in 0
end1[i] strings of length i ending in 1
Then both transitions are forced. A 0 may follow anything; a 1 may follow
only a 0:
end0[i] = end0[i-1] + end1[i-1]
end1[i] = end0[i-1]
Add them and the total satisfies total[i] = total[i-1] + total[i-2], which is
Fibonacci. The counts for n = 1, 2, 3, 4 are 2, 3, 5, 8, and recognising that
is the pleasant part of the problem, not the method.
This is the same repair as problem 411, with a smaller alphabet: when a constraint looks one step back, put that step in the state.