Как вы определяете проблему как подходящую для динамического программирования?

19

Я читал о динамическом программировании в последнее время. Хотелось бы услышать от кого-то, кто начал с нуля, и теперь довольно хорошо выявляет и решает проблемы DP. Я изо всех сил пытаюсь идентифицировать эти проблемы как DP и формулировать краткое решение.

Я прошел через большинство проблем начинающих DP и ресурсов MIT и т. Д.

user110036
источник

Ответы:

17

Я родом из физики, и, следовательно, много математики. Я нахожу легко обнаружить проблемы, хорошо подходящие для рекурсивного / динамического программирования, находя сходства с доказательством по индукции .

В доказательстве по индукции у вас есть две части:

  • Вы доказываете, что если что-то верно для итерации N, это также верно для итерации N + 1
  • Вы доказываете, что это верно для итерации 1

В рекурсивном программировании / динамическом программировании:

  • вы определяете условие выхода (например, вы жестко связываете решение для итерации 1)
  • Вы рассчитываете решение для итерации N с учетом решения для итерации N-1

Итак, как ответили другие, это вопрос опыта и выбора подсказок, но вы можете повторно использовать другие навыки, чтобы направлять вас. После этого вам нужно всегда иметь две части, которые я упомянул: если нет, то это не сработает.

Например, чтобы сгенерировать все перестановки набора:

  • условие выхода: если у вас есть только один элемент, верните его
  • рекурсия: перестановки набора из N элементов - это N наборов перестановок, которые вы получаете, выбирая каждый элемент и комбинируя их со всеми N-1 наборами (многих) перестановок подмножества, которые вы получаете, удаляя элемент.
Sklivvz
источник
8

Большинство проблем динамического программирования могут быть решены с помощью запоминания. Мемоизация обычно более интуитивна и проще в написании кода. Может оказаться полезным думать с точки зрения запоминания вместо DP.

Обычно легче понять, хорошо ли подходит проблема для запоминания (шаги такие же, как и у ответа Сливвз , но я думаю, что умственный сдвиг немного короче). Однако, как только вы решили проблему с помощью заметок, вы можете проверить, как заполняется ваш кеш заметок, а затем заполнить его по порядку, без рекурсии ... что превращает ваш алгоритм в алгоритм динамического программирования.

TL; DR; версия: вам может быть проще понять динамическое программирование с точки зрения запоминания.

См. Также StackOverflow: динамическое программирование и запоминание: восходящие и нисходящие подходы .

Брайан
источник
4

Динамическое программирование определенно о двух вещах:

  1. Оптимальная субструктура
    Большие решения могут быть получены из меньших решений; решение не является двунаправленным.

  2. Перекрывающиеся подзадачи
    . Небольшие решения будут многократно использоваться. Если подзадачи не перекрываются вообще, то вы не извлекаете выгоду из DP / памятки; то, что у вас есть, это разделяй и властвуй вместо этого.

Общий подход к проблемам DP:

  • Напишите наивную рекурсивную или итеративную версию, которая работает.

  • Обратите внимание, что функция выполняет избыточную работу.

  • Найдите способ избежать выполнения этой избыточной работы, часто путем запоминания.

Джон Перди
источник
Все это верно с теоретической точки зрения. ИМО нужно немного больше практики, чтобы быть более знакомым с быстрой идентификацией :)
user110036
2

Я никогда не реализовывал ни одного решателя динамического программирования - я занимался математикой / физикой / числовыми вычислениями, а не CS - до тех пор, пока несколько лет назад я не начал заниматься проблемами Project Euler . Решаемые DP проблемы там (например, 76 , 158 , 161 , 242, но их гораздо больше) оказалось в значительной степени мой любимый вид. Вы определенно становитесь лучше в поиске, когда это будет полезная техника: в основном ищите вещи, которые, кажется, могут быть решены с помощью какого-то рекурсивного подхода «разделяй и властвуй», где также можно приручить взрыв путей, нуждающихся быть изученным путем распознавания повторяющихся подзадач и повторного использования ранее вычисленных результатов; способность определить минимальный вектор состояния, о котором следует помнить - и какую несущественную «историю» можно стереть - является решающим шагом.

timday
источник