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

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

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

Как отвечать

Сначала уточните условие: длина n, алфавит из 0 и 1, две единицы подряд запрещены. Проверьте на маленьких значениях: при длине 1 строк две, при длине 2 три (00, 01, 10), при длине 3 пять.

Рекуррентность выводится из первого символа. Если строка начинается с 0, остаток это любая допустимая строка длины n-1. Если с 1, следом обязан идти 0, а остаток имеет длину n-2. Отсюда f(n) = f(n-1) + f(n-2) с базой f(0) = 1 (пустая строка) и f(1) = 2. Это числа Фибоначчи со сдвигом на два.

Решение за O(n) по времени и O(1) по памяти:

def count_sequences(n: int) -> int:
    if n < 0:
        raise ValueError("n не может быть отрицательным")
    prev, cur = 1, 2
    for _ in range(n):
        prev, cur = cur, prev + cur
    return prev

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

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

Генерируют все строки через itertools.product и фильтруют по "11" not in s. Это O(2^n · n), и уже при длине 30 строк больше миллиарда.

Пишут рекурсию без мемоизации и получают экспоненциальное время. С functools.cache время становится линейным, но при n порядка тысячи рекурсия упирается в RecursionError: лимит глубины по умолчанию 1000.

Забывают про n = 0 и отрицательный ввод. Решение с массивом и строкой dp[1], dp[2] = 2, 3 при нулевой длине падает с IndexError, хотя правильный ответ 1: пустая строка тоже подходит.