Конспект раздела: динамическое программирование

Понятия

Перекрытие подзадач - одна подзадача нужна многим. Оптимальная подструктура - оптимум целого содержит оптимумы подзадач.

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

Мемоизация - рекурсия плюс кеш. Таблица - цикл в правильном порядке.

Маска - подмножество, закодированное числом.

Что унести

Весь раздел - это один порядок действий, от условия задачи до кода.

ОТ РЕКУРСИИ К ТАБЛИЦЕ: ПЯТЬ ШАГОВ

0. ПРОВЕРИТЬ ДВА УСЛОВИЯ
   перекрытие подзадач       нет → хватит деления пополам (раздел 13)
   оптимальная подструктура  нет → динамика ДАСТ НЕВЕРНЫЙ ОТВЕТ

1. НАПИСАТЬ РЕКУРСИЮ В ЛОБ (можно не запускать)
2. ВЫПИСАТЬ ПАРАМЕТРЫ = состояние
3. НАЙТИ БАЗУ
4. ОЦЕНИТЬ ЦЕНУ = число состояний × цена перехода
   не влезает → сжать состояние или сменить его
5. ВЫБРАТЬ ПОРЯДОК (мемоизации он не нужен)

и только потом, последним шагом:
6. СВЕРНУТЬ ПАМЯТЬ - после проверки правильности на полной таблице

ПРОВЕРКА ПОДСТРУКТУРЫ
разрезать оптимальный ответ по подзадаче: оптимален ли кусок?
беда приходит, когда подзадачи делят ОБЩИЙ РЕСУРС
лечение - внести ресурс в состояние (остаток места, номер по порядку,
число взятых, маска использованного)

Главные числа раздела. Наивный Фибоначчи при n = 20 вызывает тело 21 891 раз при 21 состоянии (мемоизация - 39 вызовов, таблица - 20); на n = 25 наивная версия не укладывается в предел шагов. Размен 150 монетами 1, 34, 35, 39: жадность 36 монет, динамика 6. Рюкзак (10,60), (20,100), (30,120) при C = 50: 220 против 160 у жадности; на двенадцати предметах весом 28-35 при C = 60 жадность теряет треть цены (95 против 147). LCS «АЛГОРИТМ»/«ЛОГАРИФМ» = 5, общая ПОДСТРОКА = 2, Левенштейн = 4, без замены = 6. Свёрнутый рюкзак с обходом вперёд: 300 вместо 220. Коммивояжёр: перебор перестановок не уложился на 8 городах, маски дошли до 10 за 153 906 шагов.

ТРИ ПРИЁМА, КОТОРЫЕ ЗАКРЫВАЮТ БОЛЬШИНСТВО ЗАДАЧ
пара префиксов (i, j)     две строки, две стопки, две последовательности
остаток ресурса           рюкзак, монеты, бюджет, время
маска подмножества        «каждый ровно один раз» при n <= 20

Восстановление ответа - вторая половина работы: таблица даёт число, а нужен набор, строка или список правок. Обратный проход стоит O(n + m) поверх готовой таблицы, но требует её ЦЕЛИКОМ. Свёртка памяти эту возможность отнимает; вернуть её можно таблицей стрелок (два бита на клетку) или приёмом Хиршберга (Θ(n+m) памяти, время вдвое).

Связь с соседними разделами. Жадность (раздел 14) - это динамика, в которой на каждом шаге достаточно ОДНОГО варианта, и матроидность - условие, при котором это так для максимума суммы весов (у других жадных задач, вроде занятий, - свои доказательства обменом). Деление пополам (раздел 13) - динамика без перекрытий. Флойд-Уоршелл (раздел 11) - динамика по параметру «какие вершины разрешены», причём его трёхмерная таблица уже свёрнута по памяти, и именно поэтому порядок циклов там критичен.

Тихие ошибки раздела: начинать с таблицы вместо рекурсии; проверить перекрытие и забыть подструктуру; взять ноль за признак «ещё не считали»; писать в кеш до вычисления; лишний параметр (цена умножается) или недостающий (ответ неверен); i вместо i−1 в переходе рюкзака; нули в базе Левенштейна; обход вместимости вперёд у свёрнутого рюкзака; обход масок по убыванию; свёртка до проверки правильности; попытка восстановить ответ по свёрнутой таблице.

Куда это ведёт

Дальше - перебор и его сокращение: задачи, где ни жадность, ни динамика не дают точного ответа за приемлемое время. Там разбираются поиск с возвратомРазбирается в разделе 16, глава «Поиск с возвратом и отсечения»: Поиск с возвратом: проверять на входе в ветку, а не на дне, отсечения по оценкеРазбирается в разделе 16, глава «Поиск с возвратом и отсечения»: Отсечения: по оценке, по симметрии и по порядку переменных и метод ветвей и границ - то есть как перебирать, но не всё. И ровно там становится видно, зачем в этом разделе было нужно умение считать цену до написания кода: отсечение имеет смысл только если знаешь, что именно отсекаешь.