Подсчёт битовых строк без соседних единиц

Условие

Определите количество бинарных последовательностей длиной n, в которых не встречается пара соседних единичных битов.

Ответ

Количество удовлетворяет F(n)=F(n−1)+F(n−2), где F(0)=1 и F(1)=2. Это числа Фибоначчи со сдвигом индекса.

Корректная строка заканчивается либо нулём после любой допустимой строки длины n−1, либо 01 после допустимого префикса длины n−2. Эти случаи не пересекаются.

def count_strings(n):
    if type(n) is not int or n < 0:
        raise ValueError('Длина должна быть неотрицательным целым')
    current, following = 1, 2
    for _ in range(n):
        current, following = following, current + following
    return current

Для n=2 допустимы 00, 01, 10, поэтому ответ 3; для n=3 — 5. Пустая строка считается одним вариантом. Число итераций O(n), хранятся только два целых значения.