Dynamic Programming

Наивная рекурсия для числа способов подняться по лестнице вызывает себя дважды на каждом шаге: получается дерево из $2^n$ вызовов. При этом различных вопросов в нём всего $n$ — «сколькими способами дойти до ступеньки k». Каждый из них решается заново тысячи раз.

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

Экспонента превращается в произведение: число состояний, умноженное на стоимость одного перехода. Вся сложность задачи переезжает из кода в выбор состояния — и именно этот выбор и есть настоящая работа.

ступеньки:  1   2   3   4

dp[1] = 1
dp[2] = 2
dp[3] = dp[2] + dp[1] = 3
dp[4] = dp[3] + dp[2] = 5

большая задача собрана из двух уже решённых меньших

          ""   A   C
    ""     0   0   0
    A      0   1   1
    B      0   1   1
    C      0   1   2

dp[i][j] -- ответ для первых i символов первой строки и первых j второй
символы совпали  ->  dp[i-1][j-1] + 1
не совпали       ->  max(dp[i-1][j], dp[i][j-1])

Таблица заполняется сверху вниз и слева направо, потому что каждая клетка смотрит только вверх, влево и по диагонали — то есть на уже посчитанное. Ответ — в правом нижнем углу, а сам путь восстанавливается обратным ходом по таблице.

from functools import lru_cache

def distance(a, b):
    @lru_cache(maxsize=None)
    def go(i, j):
        if i == 0: return j      # осталось вставить j символов
        if j == 0: return i      # осталось удалить i символов
        if a[i - 1] == b[j - 1]:
            return go(i - 1, j - 1)
        return 1 + min(
            go(i - 1, j),        # удаление
            go(i, j - 1),        # вставка
            go(i - 1, j - 1),    # замена
        )
    return go(len(a), len(b))

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

Нужны два свойства, и оба существенны. Оптимальная подструктура: оптимальное решение задачи собирается из оптимальных решений подзадач — иначе запоминать ответ подзадачи бессмысленно, он может не подойти. Перекрывающиеся подзадачи: одни и те же подзадачи встречаются многократно — иначе кеш не даёт ничего, и это обычное разделяй-и-властвуй.

Отсюда же оценка сложности. Каждое состояние вычисляется один раз, значит суммарная работа — число состояний, умноженное на стоимость перехода. Именно поэтому «плохое» состояние (слишком много параметров) убивает решение: дело не в коде, а в размере пространства.

Два параметра реализации, не меняющие сути: сверху вниз с мемоизацией (пишется быстрее, считает только нужные состояния, упирается в глубину рекурсии) или снизу вверх таблицей (предсказуемая память, легко сокращается до пары строк).

• Неудачное состояние. Если в нём оказывается три и больше измерений, обычно часть информации выводится из остального — и её не нужно хранить.
• Забытая база. Рекурсия без базы падает по глубине, таблица без базы заполняется нулями и молча врёт.
• Порядок заполнения. Клетка, читающая ещё не посчитанную, — самая незаметная ошибка в табличном варианте.
• Восстановление ответа. Число найдено, а сам набор предметов или сама строка — нет: для этого нужны либо указатели переходов, либо повторный проход по таблице.
• Память. Таблица $n\times m$ на больших входах не помещается; если переход смотрит на предыдущую строку, храните две строки.
• Глубина рекурсии. Мемоизация на цепочке в миллион состояний упирается в лимит стека — переходите к таблице.

1. Назовите два свойства задачи, без которых динамика бессмысленна.
2. Лестница: во что превращается решение, если убрать кеш, и почему?
3. Расстояние Левенштейна: что означает клетка dp[i][j] и откуда в неё приходят значения?
4. Рюкзак: как восстановить не только максимальную стоимость, но и сам набор предметов?
5. Когда мемоизация хуже таблицы, а когда лучше?