415. 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.

Constraints - `1 ≤ n ≤ 88` - The answer fits in a signed 64-bit integer.