Что такое динамическое программирование?

Подход применим, когда:

• оптимальная подструктура — оптимальный ответ строится из оптимальных ответов на подзадачи;
• перекрывающиеся подзадачи — одни и те же подзадачи встречаются многократно (в отличие от «разделяй и властвуй», где части независимы).

Как решать:

1. Состояние — что описывает подзадачу: dp[i] — ответ для первых i элементов, dp[i][j] — для префиксов двух строк.
2. Переход — как ответ выражается через меньшие подзадачи.
3. База — ответы для самых маленьких подзадач.
4. Порядок — так, чтобы нужные значения были посчитаны раньше.

Два способа реализации:

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

Классические задачи: числа Фибоначчи, число способов подняться по лестнице, рюкзак 0/1, наибольшая общая подпоследовательность (LCS), расстояние редактирования (Левенштейна), размен монет.

Отличие от жадного алгоритма: жадный делает локально лучший выбор и не пересматривает его — быстро, но верно только для задач со специальной структурой (размен монет 1/5/10 — да, 1/3/4 — нет). Динамическое программирование перебирает все варианты через подзадачи и гарантирует оптимум.

def knapsack(items, capacity):
    """items: [(вес, ценность)] — максимальная ценность в рюкзаке вместимостью capacity."""
    dp = [0] * (capacity + 1)                 # dp[c] — лучшая ценность при вместимости c
    for weight, value in items:
        for c in range(capacity, weight - 1, -1):   # с конца, чтобы взять предмет один раз
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]

knapsack([(1, 1), (3, 4), (4, 5), (5, 7)], 7)   # 9: предметы весом 3 и 4