Урок

Динамика: от рекурсии к таблице

Представь лестницу

Перед тобой лестница из n ступенек. За один шаг можно подняться на 1 или на 2 ступеньки. Сколькими способами можно добраться до верха?

Начни с конца. На последнюю ступеньку n ты попадаешь одним из двух способов:

шагнул на 1 со ступеньки n-1;
шагнул на 2 со ступеньки n-2.

Значит, число путей до n равно числу путей до n-1 плюс числу путей до n-2:

ways(n) = ways(n-1) + ways(n-2)

Ты только что разбил большую задачу на две поменьше. Вся динамика держится на этом приёме.

Два признака динамики

Оптимальная подструктура. Ответ на большую задачу собирается из ответов на маленькие. Ответ для n складывается из ответов для n-1 и n-2, и больше ничего знать не нужно.

Перекрывающиеся подзадачи. Одни и те же маленькие задачи встречаются снова и снова. Посмотри на дерево вызовов для n = 5:

Дерево вызовов ways(5): ways(3) считается дважды, ways(2) — трижды

ways(3) вычисляется дважды, ways(2) трижды. При n = 40 повторов будут миллионы, и наивная рекурсия работает за O(2^n).

Если в задаче есть оба признака, перед тобой почти наверняка динамика.

Путь в четыре шага

Шаг	Идея	Время	Память
1. Рекурсия	считаем «в лоб» по формуле	`O(2^n)`	`O(n)` стек
2. Мемоизация	запоминаем уже посчитанное в словаре	`O(n)`	`O(n)`
3. Таблица снизу вверх	заполняем массив `dp` от малых к большим	`O(n)`	`O(n)`
4. Экономия памяти	храним только два последних значения	`O(n)`	`O(1)`

Мемоизация — та же рекурсия, но перед вычислением ты заглядываешь в «блокнот»: если ways(k) уже считали, сразу возвращаешь сохранённое. Каждое k считается один раз.

Таблица переворачивает рекурсию. Вместо спуска сверху ты идёшь снизу: сначала маленькие ответы, потом из них большие. Рекурсии нет, стек не переполнится.

i-2 ↓ 33

i-1 ↓ 54

i ↓ 85

136

dp[5] = dp[4] + dp[3] = 5 + 3 = 8 — каждая клетка зависит от двух предыдущих

Видно, что для dp[i] нужны только две соседние клетки слева. Всё, что левее, уже не понадобится. Поэтому весь массив можно заменить двумя переменными. Это и есть экономия памяти.

Таблица снизу вверх

def climb_stairs(n: int) -> int:
    # dp[i] — число способов добраться до ступеньки i
    dp = [0] * (n + 1)
    dp[0] = 1                      # база: на земле — один способ (стоять)
    if n >= 1:
        dp[1] = 1                  # база: на первую ступень — один шаг
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # переход
    return dp[n]                   # ответ

Экономия памяти: O(1)

def climb_stairs(n: int) -> int:
    prev2, prev1 = 1, 1            # dp[i-2] и dp[i-1]
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2   # сдвигаем «окно»
    return prev1

Как это звучит на собесе

Интервьюер ждёт не сразу код, а четыре чёткие фразы. Проговори их вслух, прежде чем писать:

Состояние: «dp[i] — число способов добраться до ступеньки i». Главное — сказать, что означает клетка.
Переход: «На ступеньку i можно прийти с i-1 или с i-2, поэтому dp[i] = dp[i-1] + dp[i-2]».
База: «dp[0] = 1, dp[1] = 1, это самые маленькие случаи, которые не выводятся из формулы».
Ответ: «Ответ лежит в dp[n]».

Дальше добавь: «Сложность O(n) по времени. Каждый шаг смотрит только на два предыдущих значения, поэтому память сжимается до O(1)». Это сразу показывает, что ты понимаешь приём, а не помнишь задачу наизусть.

Застрял в незнакомой задаче? Сначала напиши честную рекурсию, добавь мемоизацию и только потом переводи в таблицу. Так ты почти всегда дойдёшь до решения.

Частые ошибки

Размытое состояние. «Ну, dp — это что-то про ступеньки» не годится. Без точного смысла клетки не получится ни переход, ни база.
Забытая или неверная база. Если dp[0] = 0, всё обнулится. Проверяй базу на крошечных n руками: при n = 2 способов должно быть 2.
Выход за границы. При n = 0 или n = 1 обращение к dp[1] или к dp[i-2] может упасть. Защищайся проверками.
Неправильный порядок заполнения. Таблицу заполняют так, чтобы к моменту вычисления dp[i] всё нужное уже было посчитано.
Ранняя экономия памяти. Сначала добейся рабочей таблицы, сжимать её стоит потом. Иначе легко перепутать порядок присваиваний.

Теперь у тебя есть полный путь: формула, рекурсия, мемоизация, таблица и сжатие. Дальше в главе ты пройдёшь этот путь сам на новых задачах.