235. Strings With No Two Ones Together

Print how many binary strings of length n contain no two 1s next to each other.

n = 3 -> 000 001 010 100 101 is 5

Build the string one character at a time and the choice at each step depends only on what the previous character was. After a 0 you may place either digit; after a 1 you must place a 0.

So the state is just the length remaining and whether the last character was a one, which is two numbers rather than the whole string.

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