Простой пример для тех, кто хочет понять динамическое программирование [закрыто]

96

Я ищу легко понятный пример для тех, кто хочет изучить динамическое программирование. Здесь есть хорошие ответы о том, что такое динамическое программирование . Последовательность Фибоначчи - отличный пример, но она слишком мала, чтобы поцарапать поверхность. Похоже, это отличный предмет для изучения, хотя я еще не изучал класс алгоритмов, надеюсь, он в моем списке на весну.

Арак
источник

Ответы:

30

Посетите этот сайт: Проблемы практики динамического программирования

Ник Дандулакис
источник
1
Просмотр этой лекции на сайте MIT video.mit.edu/watch/… и последующее решение вышеуказанных проблем поможет вам понять, почему DP полезен.
pg2286
Например, ссылка на YouTube в комментарии уже не работает. Новая ссылка: youtube.com/watch?v=OQ5jsbhAv_M
AJP
Посмотрите этот набор видеороликов, которые, как я обнаружил, довольно интуитивно охватывают аспекты алгоритмов как сверху вниз, так и снизу вверх: youtube.com/playlist?list=PLx-Ye3Zw0WL0O_IDmbcVHlKqJuGEfw3VG
william007
Похоже, MIT переместил свой контент с главной страницы на страницу MIT OpenCourseWare, поэтому предоставленная ссылка @ pg2286 недействительна. Ссылка теперь 19. Динамическое программирование I Также доступен полный плейлист « Введение в алгоритмы»
rite2hhh
7

Идея динамического программирования заключается в том, что вы кэшируете (запоминаете) решения подзадач, хотя я думаю, что это еще не все.

Есть много проблем с Google Code Jam, для решения которых требуется динамическое программирование. Примеры:

Добро пожаловать в Code Jam (умеренный)

Обман булева дерева (умеренный)

PermRLE (жесткий)

Обратите внимание, что в каждом практическом конкурсе Code Jam есть раздел «Анализ конкурса» на случай, если вы в тупике пытаетесь решить проблему.

Джои Адамс
источник
Спасибо за ресурсы. Время от времени я решаю один или два вопроса из проекта euler, и мне кажется, что я действительно застрял на некоторых проблемах, которые требуют знания DP.
AraK
5
  1. У гиков для гиков есть большая коллекция задач динамического программирования. Я считаю, что этот набор - один из лучших, если вы готовитесь к собеседованию.
  2. Если вам нужны небольшие обучающие видеоролики по проблемам DP, вы можете проверить этот набор задач в MIT.
Диптенду
источник
4

Вычисление расстояний Левенштейна было одной из первых задач, которые я решил с помощью динамического программирования; Я думаю, что это достойный следующий шаг от последовательности Фибоначчи с точки зрения сложности.

http://en.wikipedia.org/wiki/Levenshtein_distance

Дэвид Уинслоу
источник