Как найти количество битовых последовательностей длины n без подряд идущих единиц

Что проверяют

Умеете ли вы вывести рекуррентность из структуры задачи, а не узнать по памяти ответ «это Фибоначчи». Следом просят сократить память, посчитать ответ для огромного n или вывести сами последовательности.

Как отвечать

Рассуждение через состояния понятнее готовой формулы. Пусть a[i] это число допустимых строк длины i, оканчивающихся на 0, а b[i] на 1:

• 0 можно дописать к любой строке: a[i] = a[i-1] + b[i-1];
• 1 дописывается только после 0: b[i] = a[i-1];
• ответ: a[n] + b[n], база a[1] = b[1] = 1.

Отсюда f(n) = f(n-1) + f(n-2) с f(1) = 2 и f(2) = 3, то есть f(n) совпадает с числом Фибоначчи номер n + 2. Код без массива, O(n) по времени и O(1) по памяти:

def count(n: int) -> int:
    end0, end1 = 1, 0  # пустая строка
    for _ in range(n):
        end0, end1 = end0 + end1, end0
    return end0 + end1

Проверка: count(0) == 1, count(3) == 5, count(5) == 13. Целые в Python не переполняются, но длина числа в битах растёт линейно по n, поэтому на собеседовании часто просят ответ по модулю 10**9 + 7. Для очень больших n матрицу [[1, 1], [1, 0]] возводят в степень бинарным алгоритмом: O(log n) умножений.

Покажите и проверку перебором для малых n: sum('11' not in ''.join(p) for p in itertools.product('01', repeat=n)). Такой тест за секунду ловит ошибку в базе.

Где спотыкаются

Пишут рекурсию f(n-1) + f(n-2) без мемоизации. Время растёт экспоненциально, и уже при n = 40 ответа ждут очень долго. Хватит functools.cache или цикла.

Путают базу: по привычке к Фибоначчи ставят f(1) = 1 и получают сдвиг. Первые значения стоит сверить руками на n = 1, 2, 3.

Забывают про n = 0. Пустая строка подходит под условие, ответ 1, а решение, которое заранее пишет в dp[1] и dp[2], на таком входе падает с IndexError.