В предыдущем уроке вы познакомились с идеями мемоизации и таблирования на примере Фибоначчи. Теперь — полноценный разбор всех подходов к этой задаче и демонстрация того, что «задача о Фибоначчи» это целое семейство задач. Многие счётные задачи на собеседованиях, которые кажутся несвязанными, в итоге сводятся к одному рекуррентному соотношению: f(n) = f(n-1) + f(n-2). Четыре подхода: сравнение**

Сформулируем задачу строго: найти F(n), где F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) при n ≥ 2. Сравним четыре способа.

Подход 1 — наивная рекурсия. Прямое кодирование определения. Время O(2ⁿ), память O(n) (стек). Допустима только для n ≤ 30.

long FibNaive(int n)
{
    if (n <= 1) return n;
    return FibNaive(n - 1) + FibNaive(n - 2);
}

Подход 2 — мемоизация. Рекурсия + словарь-кеш. Каждое значение вычисляется один раз. Время O(n), память O(n).

static Dictionary<int, long> _memo = new();

static long FibMemo(int n)
{
    if (n <= 1) return n;
    if (_memo.TryGetValue(n, out long cached))
        return cached;

    long result = FibMemo(n - 1) + FibMemo(n - 2);
    _memo[n] = result;
    return result;
}

Подход 3 — таблирование. Итеративное заполнение массива от 0 до n. Без рекурсии — без риска переполнения стека. Время O(n), память O(n).

static long FibTab(int n)
{
    if (n <= 1) return n;
    long[] dp = new long[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Подход 4 — оптимизация памяти. Два «скользящих» значения вместо массива. Время O(n), память O(1). Лучшее практическое решение для больших n.

static long FibOptimal(int n)
{
    if (n <= 1) return n;
    long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++)
    {
        long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Итоговая таблица для n = 10 000: наивная рекурсия — не завершится никогда; мемоизация — переполнение стека в .NET; таблирование — работает, 10 000 элементов; оптимизация — работает, 2 переменные. При n = 10 000 лучший выбор — таблирование или оптимизация. При n = 92 все четыре (кроме наивной) дают одинаковый ответ в рамках long; при n ≥ 93 нужен BigInteger. Матричное возведение в степень: O(log n)**

Существует способ вычислить F(n) ещё быстрее — за O(log n). Он основан на следующем тождестве:

// [F(n+1)]   [1 1]^n   [F(1)]
// [F(n)  ] = [1 0]   * [F(0)]
//
// То есть: если возвести матрицу [[1,1],[1,0]] в степень n,
// верхний левый элемент результата равен F(n+1).

Быстрое возведение в степень (метод «возведение в квадрат») делит показатель пополам на каждом шаге, давая O(log n) умножений матриц. Каждое умножение матриц 2×2 — O(1) операций. Итог: O(log n) для F(n) любой величины.

using System.Numerics;

// Матрица 2x2 как массив long[2,2]
static long[,] MatMul(long[,] A, long[,] B)
{
    return new long[,]
    {
        { A[0,0]*B[0,0] + A[0,1]*B[1,0],  A[0,0]*B[0,1] + A[0,1]*B[1,1] },
        { A[1,0]*B[0,0] + A[1,1]*B[1,0],  A[1,0]*B[0,1] + A[1,1]*B[1,1] }
    };
}

static long[,] MatPow(long[,] M, int p)
{
    // Единичная матрица — нейтральный элемент умножения
    long[,] result = { { 1, 0 }, { 0, 1 } };
    while (p > 0)
    {
        if (p % 2 == 1)
            result = MatMul(result, M); // нечётный показатель — домножаем
        M = MatMul(M, M);               // возводим в квадрат
        p /= 2;
    }
    return result;
}

static long FibMatrix(int n)
{
    if (n <= 1) return n;
    long[,] M = { { 1, 1 }, { 1, 0 } };
    long[,] R = MatPow(M, n);
    return R[0, 1]; // R[0,1] = F(n), R[0,0] = F(n+1)
}

Console.WriteLine(FibMatrix(10));  // 55
Console.WriteLine(FibMatrix(50));  // 12586269025

В рамках конкурсных задач матричный метод используется, когда n ≥ 10¹⁸ или когда рекуррентное соотношение более сложное (например, F(n) = aF(n-1) + bF(n-2) + c — линейная рекуррентность произвольного порядка). Для типичных интервью достаточно O(n)-решения. Но знать о матричном методе полезно: он обобщается на целый класс задач.

Задачи, сводящиеся к Фибоначчи**

Суть применения DP — не запоминание конкретных задач, а распознавание рекуррентного соотношения. Покажем три задачи, которые по структуре совпадают с Фибоначчи.

Подъём по лестнице (Climbing Stairs). За один шаг можно подняться на 1 или 2 ступеньки. Сколько различных способов подняться на n-ю ступеньку?

Ключ: чтобы оказаться на ступеньке n, нужно прийти либо со ступеньки n-1 (один шаг), либо со ступеньки n-2 (два шага). Значит, ways(n) = ways(n-1) + ways(n-2). Базовые случаи: ways(1) = 1, ways(2) = 2. Это Фибоначчи со смещёнными начальными значениями.

static int ClimbStairs(int n)
{
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2; // ways(1) = 1, ways(2) = 2
    for (int i = 3; i <= n; i++)
    {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Console.WriteLine(ClimbStairs(4));  // 5: (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)
Console.WriteLine(ClimbStairs(10)); // 89

Укладка плитки. Сколько способов выложить дорожку 2×n плитками 2×1? Каждую плитку можно положить вертикально или горизонтально. Вертикальная занимает одну «колонку» 2×1, горизонтальная — пара занимает 2×2. Рекуррентность та же: tile(n) = tile(n-1) + tile(n-2), базы tile(1) = 1, tile(2) = 2.

static int TileWays(int n)
{
    // Та же формула, что ClimbStairs — только смысл другой
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}

Console.WriteLine(TileWays(4));  // 5
Console.WriteLine(TileWays(6));  // 13

Подсчёт путей в сетке. Немного отличающийся вариант — число путей из левого верхнего угла в правый нижний угол сетки m×n (движение только вправо или вниз). Здесь уже двумерная DP, но идея та же.

static int GridPaths(int m, int n)
{
    // dp[i][j] = число путей в клетку (i, j)
    int[,] dp = new int[m, n];

    // Первая строка и первый столбец — только один путь (всё время вправо / вниз)
    for (int i = 0; i < m; i++) dp[i, 0] = 1;
    for (int j = 0; j < n; j++) dp[0, j] = 1;

    // Переход: в (i,j) можно попасть сверху (i-1,j) или слева (i,j-1)
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i, j] = dp[i - 1, j] + dp[i, j - 1];

    return dp[m - 1, n - 1]; // правый нижний угол
}

Console.WriteLine(GridPaths(3, 3)); // 6
Console.WriteLine(GridPaths(3, 7)); // 28

В задаче GridPaths рекуррентное соотношение уже двумерное — dp[i][j] зависит от dp[i-1][j] и dp[i][j-1]. Базовые случаи — вся первая строка и весь первый столбец. Оптимизация памяти здесь тоже применима: достаточно хранить одну строку dp и обновлять её слева направо.

Все три задачи объединяет одно: чтобы найти число способов сделать что-то с n объектами, подумайте о последнем шаге — откуда вы могли прийти в состояние n? Если есть k вариантов предыдущего шага, рекуррентность f(n) = сумма f(предыдущих состояний). Это и есть стандартный шаблон DP для счётных задач.