Конспект: перекрытие подзадач и оптимальная подструктура

Понятия

Перекрытие подзадач - одна и та же подзадача нужна многим; без запоминания считается заново.

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

Состояние - минимум сведений о прошлом, нужный для будущего.

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

Что унести

ДВА УСЛОВИЯ
перекрытие подзадач      → про ЦЕНУ: нет его - динамика не нужна
оптимальная подструктура → про ПРАВИЛЬНОСТЬ: нет её - динамика неверна

ЦЕНА = число состояний × цена одного перехода

РЕЦЕПТ ИЗ ПЯТИ ШАГОВ
1. написать рекурсию в лоб (можно не запускать)
2. выписать параметры = состояние
3. найти базу
4. оценить цену; дорого - вернуться к шагу 2 и сжать состояние
5. выбрать порядок (у мемоизации получается сам)

Разных состояний при n = 20 - двадцать одно; наивная рекурсия вызывает тело 2·f(21) − 1 = 21 891 раз. Кеш проверяют ДО вычисления и пишут ПОСЛЕ: наоборот - программа останется верной и экспоненциальной.

Проверка подструктуры: разрезать оптимальный ответ по подзадаче и спросить, оптимален ли кусок.

Контрпример для длинного пути: в графе q→r, r→t, q→s, s→t, t→r оптимальный q→r - это q→s→t→r (3 ребра), и приклеить к нему r→t нельзя: t уже посещён. А настоящий оптимум q→t = q→r→t содержит НЕоптимальный кусок q→r.

Типовые состояния: «сколько рассмотрено» (индекс), «сколько ресурса осталось», «где я», «что из чего» (два индекса), «в каком режиме» (флаг), «какое подмножество использовано» (маска - только при n <= 20).

ПАРАМЕТР НУЖЕН ⇔ без него две ситуации с РАЗНЫМ БУДУЩИМ попадают в одну клетку
лишний параметр  → цена умножается, ответ верен
недостающий      → ответ неверен, и молча

Размен монет: состояние - ОДНО число, остаток суммы. На монетах 1, 34, 35, 39 и сумме 150 жадность даёт 36 монет (три по 39 плюс 33 единицы), динамика - 6 (35+35+39+39+1+1). Цена Θ(S·k).

Тихие ошибки: начинать с таблицы вместо рекурсии; проверить только перекрытие; взять ноль за признак «не считали»; забыть базу; не посчитать цену до написания кода; мемоизировать функцию, которая зависит не только от аргументов.

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

Следующая глава - три классические задачи с двумерной таблицей: целый рюкзак, наибольшая общая подпоследовательность и расстояние редактирования. Там же появляется вторая половина работы - ВОССТАНОВЛЕНИЕ ответа: таблица даёт число, а нужен обычно сам набор предметов, сама подпоследовательность или сам список правок.