Как вы думаете, есть ли у упражнения динамическое программирование или нет?Если есть, то как вы разрабатываете алгоритм для его решения?

Question

Каким условиям должна соответствовать задача программирования, чтобы ее можно было решить с помощью динамического программирования?Какие рассуждения вы делаете для того, чтобы выяснить это?

Как только вы решите, что у него действительно есть решение DP, тогда как вы будете продолжать создавать алгоритм DP, который его решает?Какова логика создания таких алгоритмов?

Answer 1

Проблема должна удовлетворять двум условиям, чтобы ее можно было решить с помощью динамического программирования. Цитирование Введение в алгоритмы , глава 15:

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

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

В Руководстве по проектированию алгоритмов , глава 8, автор описывает три шага, связанных с решением проблемы с помощью динамического программирования:

1. Сформулируйте ответ как рекуррентное отношение или рекурсивный алгоритм.
2. Покажите, что число различных значений параметров, принимаемых вашей рекуррентностью, ограничено (мы надеемся, небольшим) полиномом.
3. Укажите порядок оценки повторения, чтобы необходимые вам частичные результаты всегда были доступны, когда они вам нужны.

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