Идея динамического программирования и одномерные ДП

Главный приём олимпиад: разбить задачу на перекрывающиеся подзадачи, решить каждую один раз и переиспользовать ответы.

Динамическое программирование (ДП) — метод решения задач, при котором ответ строится из ответов на меньшие перекрывающиеся подзадачи, каждая из которых считается ровно один раз.

Зачем это нужно

Динамическое программирование — самая важная и самая часто встречающаяся тема на серьёзных олимпиадах. «Почти каждый контест уровня Gold содержит задачу на ДП», — говорят составители USACO Guide, и это правда. ДП превращает экспоненциальный перебор в полиномиальное решение, когда у задачи есть структура перекрывающихся подзадач. Освоить ДП трудно (это скорее способ мышления, чем шаблон), но без него выше определённого уровня не подняться. Начнём с самого простого — одномерных ДП.

Идея «на пальцах»: от рекурсии к ДП

Возьмём числа Фибоначчи: F(n) = F(n−1) + F(n−2). Наивная рекурсия пересчитывает одни и те же значения снова и снова: F(5) вызовет F(3) дважды, F(2) — трижды. Дерево вызовов растёт экспоненциально — O(2^n). Но подзадач-то всего n различных! Если запоминать уже посчитанные значения (мемоизация) или считать их снизу вверх в массиве, каждая подзадача решается один раз — и сложность падает до O(n). В этом вся суть ДП: не считай дважды то, что уже посчитал.

Два стиля: сверху вниз и снизу вверх

Сравним мемоизацию (рекурсия + кеш) и табличный подход (цикл по массиву) на Фибоначчи.

from functools import lru_cache

# Стиль 1: сверху вниз (мемоизация) — рекурсия с автоматическим кешем
@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

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

print("fib_memo(10) =", fib_memo(10))
print("fib_table(10) =", fib_table(10))
print("fib(30) =", fib_table(30))

@lru_cache — это готовая мемоизация: Python сам запоминает результаты по аргументам. Табличный стиль явно заполняет массив dp в правильном порядке. Оба дают O(n); выбор — дело вкуса и удобства. Табличный обычно быстрее (нет накладных расходов рекурсии) и не упирается в лимит глубины.

Вывод:

fib_memo(10) = 55
fib_table(10) = 55
fib(30) = 832040

Три кита любого ДП

Чтобы спроектировать ДП, ответь на три вопроса:

1. Состояние: что описывает dp[i]? («число способов дойти до ступени i», «макс. ценность при весе i»). Это самый творческий шаг.
2. Переход: как выразить dp[i] через меньшие dp[...]? Это рекуррентное соотношение.
3. База и порядок: чему равны начальные значения и в каком порядке считать, чтобы нужные подзадачи были готовы к моменту использования.

Задача про лесенку (способы подъёма)

Классика: сколько есть способов подняться по n ступеням, делая шаги длиной 1 или 2? Состояние dp[i] — число способов добраться до ступени i. Чтобы попасть на i, мы пришли либо с i−1 (шаг 1), либо с i−2 (шаг 2). Значит, dp[i] = dp[i−1] + dp[i−2] — то же соотношение, что у Фибоначчи!

def ways(n):
    dp = [0] * (n + 1)
    dp[0] = 1                       # один способ "стоять на месте"
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]           # шаг длиной 1
        if i >= 2:
            dp[i] += dp[i - 2]      # шаг длиной 2
    return dp[n]

print("Способов подняться по 5 ступеням:", ways(5))
print("Для 10 ступеней:", ways(10))

Здесь важна база dp[0] = 1: способ «никуда не идти» один. Дальше каждое значение складывается из двух предыдущих. Эта задача показывает, как разные формулировки сводятся к одному рекуррентному соотношению — узнавать это и есть навык ДП.

Вывод:

Способов подняться по 5 ступеням: 8
Для 10 ступеней: 89

Размен суммы (число способов)

Ещё одно одномерное ДП: сколькими способами набрать сумму S монетами заданных номиналов (порядок не важен)? Состояние dp[s] — число способов набрать сумму s. Перебираем монеты во внешнем цикле (чтобы не считать перестановки), внутри обновляем суммы.

coins = [1, 2, 5]
S = 5
dp = [0] * (S + 1)
dp[0] = 1                           # пустой набор даёт сумму 0
for c in coins:                     # каждую монету рассматриваем один раз
    for s in range(c, S + 1):
        dp[s] += dp[s - c]          # добавили монету c к набору на (s-c)
print("Способов набрать", S, ":", dp[S])
print("Все dp:", dp)

Порядок циклов критичен: монеты снаружи, суммы внутри — так каждый набор учитывается один раз (без учёта порядка монет). Для суммы 5 монетами 1,2,5 это: 5×1; 1+2+2; 1+1+1+2; 1+1+1+1+1; 5 — итого 4 способа.

Вывод:

Способов набрать 5 : 4
Все dp: [1, 1, 2, 2, 3, 4]

Как «увидеть» подзадачу: разбор на лесенке

Главная трудность ДП — не код, а умение заметить подзадачу. Полезный мысленный приём: представь, что ты стоишь в конечной точке и спрашиваешь «как я сюда попал?». Для лесенки из 4 ступеней: на ступень 4 я пришёл либо с 3 (шагнув на 1), либо с 2 (шагнув на 2). Значит, число путей до 4 — это сумма путей до 3 и до 2. Тот же вопрос рекурсивно: путей до 3 = (до 2) + (до 1), и так далее. Так задача «развернулась» в подзадачи. Проследим заполнение таблицы по шагам:

def ways_trace(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    print(f"dp[0] = 1 (базовый случай)")
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
        prev = f"dp[{i-1}]={dp[i-1]}" + (f" + dp[{i-2}]={dp[i-2]}" if i >= 2 else "")
        print(f"dp[{i}] = {prev} = {dp[i]}")
    return dp[n]

print("Ответ:", ways_trace(4))

Видно, как каждое значение строится из двух предыдущих — таблица заполняется слева направо, и к моменту расчёта dp[i] оба слагаемых уже готовы. Этот «вопрос назад» (как я попал в состояние?) — универсальный способ нащупать переход в любой задаче ДП.

Вывод:

dp[0] = 1 (базовый случай)
dp[1] = dp[0]=1 = 1
dp[2] = dp[1]=1 + dp[0]=1 = 2
dp[3] = dp[2]=2 + dp[1]=1 = 3
dp[4] = dp[3]=3 + dp[2]=2 = 5
Ответ: 5

Подводные камни

• Неправильное состояние — главная ошибка. Если dp[i] описано неточно, переход не сойдётся. Чётко формулируй, что именно хранит ячейка.
• Забытая база. dp[0] часто равен 1 (а не 0!) в задачах на подсчёт способов.
• Порядок вычисления. К моменту расчёта dp[i] все нужные подзадачи должны быть готовы.
• Мемоизация и рекурсия: глубокая рекурсия + lru_cache может упереться в лимит; на больших n предпочитай табличный стиль.

Итог

• ДП решает каждую перекрывающуюся подзадачу один раз, превращая экспоненту в полином.
• Два стиля: мемоизация (сверху вниз, lru_cache) и таблица (снизу вверх, массив).
• Проектируй ДП через три вопроса: состояние, переход, база и порядок.
• Лесенка, Фибоначчи, размен — все сводятся к простым рекуррентным соотношениям; учись их узнавать.