Алгоритмы с нуля
Dynamic programming: построить и доказать DP-решатель
Читать про DP — не то же, что выводить её под давлением. Возьмите реальную задачу оптимизации, доведите её от наивной рекурсии до таблицы с оптимизированной памятью и докажите корректность каждого шага — цикл, который вы запускаете на каждом интервью и в каждом реальном решателе.
Превратите чеклист юнита в воспроизводимый инженерный цикл: назвать state, написать transition, добавить memoization, перевести в tabulation, оптимизировать память, восстановить путь и проверить всё против независимого оракула на переборе.
Реализуйте одну нетривиальную DP-задачу от и до — edit distance, 0/1 knapsack или взвешенное планирование интервалов — проведя её от перебора через memoization, tabulation и версию с оптимизированной памятью, с восстановленным оптимальным путём решения и проверкой каждого этапа против независимого оракула.
- Рандомизированный дифференциальный тест прогоняет не менее 1000 малых случаев, сравнивая версии с memoization, tabulation и оптимизированной памятью против оракула-перебора; все совпадают по оптимальному значению.
- Восстановленный путь проверен: повторное применение его (проигрывание сценария правок, суммирование весов и ценностей выбранных предметов) воспроизводит оптимальное значение в рамках заявленных ограничений.
- Короткая таблица перечисляет временную и пространственную сложность каждой версии с однострочным обоснованием, и версия с оптимизированной памятью доказуемо использует асимптотически меньше памяти, чем полная таблица.
- Описание в один абзац называет state и transition обычными словами и объясняет, почему выбранный порядок обхода корректен (каждое чтение предшествует своей записи).
- Добавьте вторую задачу с другой формой state (например interval DP — matrix chain или burst balloons) и переиспользуйте ту же оснастку оракула для её проверки.
- Снабдите версию с memoization счётчиком попаданий и промахов кэша, а перебор — счётчиком всех вызовов; постройте график, как разрыв растёт с размером входа, делая схлопывание экспоненты в полином наглядным.
- Разберите ловушку псевдополиномиальности: для knapsack покажите, как таблица O(n*W) раздувается с ростом ёмкости W даже при немногих предметах, и обсудите, когда вместо неё нужен meet-in-the-middle или аппроксимация.
- Обобщите восстановление в переиспользуемую утилиту трассировки, которая по заполненной таблице dp и transition возвращает оптимальный путь для любого из ваших решателей.
Это цикл, который вы будете запускать на каждой DP, на интервью и в продакшн-решателях: записать рекуррентность до кода, построить доверенный оракул-перебор, затем подняться от memoization к tabulation и к окну с оптимизированной памятью, сверяясь с оракулом на каждом шаге, и наконец восстановить путь — не только значение. Сделав это раз на игрушечной задаче, следующую делаешь на автомате: назвать state, написать transition, доказать порядок, оптимизировать в последнюю очередь.