hello-algo/ru/docs/chapter_dynamic_programming/summary.md

Резюме

Ключевые моменты

• Динамическое программирование разбивает задачу на подзадачи и за счет сохранения решений подзадач избегает повторных вычислений, повышая эффективность вычислений.
• Без учета времени все задачи динамического программирования можно решить методом поиска с возвратом (полным перебором), но в дереве рекурсии существует большое количество перекрывающихся подзадач, что крайне неэффективно. Введение списка мемоизации позволяет сохранять решения всех вычисленных подзадач, тем самым гарантируя, что перекрывающиеся подзадачи вычисляются только один раз.
• Мемоизация поиска -- это рекурсивный метод «сверху вниз», в то время как соответствующее динамическое программирование -- это итеративный метод «снизу вверх», который подобен «заполнению таблицы». Поскольку текущее состояние зависит только от некоторых локальных состояний, мы можем исключить одно измерение таблицы dp, тем самым снижая пространственную сложность.
• Разбиение на подзадачи -- это универсальный алгоритмический подход, который имеет различные свойства в методах «разделяй и властвуй», динамическом программировании и поиске с возвратом.
• Задачи динамического программирования обладают тремя основными свойствами: перекрывающиеся подзадачи, оптимальная подструктура и отсутствие последействия.
• Если оптимальное решение исходной задачи можно построить из оптимальных решений подзадач, то она обладает оптимальной подструктурой.
• Отсутствие последействия означает, что для данного состояния его будущее развитие зависит только от этого состояния и не зависит от всех прошлых состояний. Многие задачи комбинаторной оптимизации не обладают свойством отсутствия последействия и не могут быть быстро решены с помощью динамического программирования.

Задача о рюкзаке

• Задача о рюкзаке -- одна из самых типичных задач динамического программирования, имеющая варианты: рюкзак 0-1, полный рюкзак, множественный рюкзак и другие.
• В задаче о рюкзаке 0-1 состояние определяется как максимальная стоимость первых i предметов в рюкзаке вместимостью c. На основе двух решений -- не класть в рюкзак и класть в рюкзак -- можно получить оптимальную подструктуру и построить уравнение перехода состояния. При оптимизации пространства, поскольку каждое состояние зависит от состояний сверху и слева сверху, необходимо обходить список в обратном порядке, чтобы избежать перезаписи состояния слева сверху.
• В задаче о полном рюкзаке количество выбираемых предметов каждого типа не ограничено, поэтому переход состояния при выборе предмета отличается от задачи о рюкзаке 0-1. Поскольку состояние зависит от состояний сверху и слева, при оптимизации пространства следует обходить в прямом порядке.
• Задача о размене монет -- это вариант задачи о полном рюкзаке. Она меняет поиск «максимальной» стоимости на поиск «минимального» количества монет, поэтому в уравнении перехода состояния \max() следует заменить на \min(). От стремления «не превысить» вместимость рюкзака к стремлению «точно» составить целевую сумму, поэтому используется amt + 1 для обозначения недопустимого решения «невозможно составить целевую сумму».
• Задача о размене монет II меняет поиск «минимального количества монет» на поиск «количества комбинаций монет», соответственно уравнение перехода состояния меняется с \min() на оператор суммирования.

Задача о редакционном расстоянии

• Редакционное расстояние (расстояние Левенштейна) используется для измерения сходства между двумя строками и определяется как минимальное количество операций редактирования для преобразования одной строки в другую, операции редактирования включают добавление, удаление и замену.
• Состояние в задаче о редакционном расстоянии определяется как минимальное количество операций редактирования, необходимых для преобразования первых i символов s в первые j символов t. Когда s[i] \ne t[j], существует три решения: добавление, удаление, замена, каждое из которых имеет соответствующую оставшуюся подзадачу. На основе этого можно найти оптимальную подструктуру и построить уравнение перехода состояния. А когда s[i] = t[j], редактирование текущего символа не требуется.
• В задаче о редакционном расстоянии состояние зависит от состояний сверху, слева и слева сверху, поэтому после оптимизации пространства ни прямой, ни обратный обход не позволяют правильно выполнить переход состояния. Для этого мы используем переменную для временного хранения состояния слева сверху, тем самым преобразуя задачу к эквивалентной задаче о полном рюкзаке, что позволяет выполнять прямой обход после оптимизации пространства.