Динамическое программирование

Рейтинг за домашнюю работу

Динамическое программирование — это когда у нас есть задача, которую непонятно

Задача про черепашку

Есть клетчатое поле NхM. В левом верхнем углу сидит

Первая основная идея ДП

Будем искать ответ не только на нашу общую

А что дальше?

Ответ для верхнего левого угла очевиден. У нас только

Вторая основная идея ДП

Решая задачу для очередной клетки, будем считать, что

А как мы можем попасть в очередную клетку?

Всё очевидно! Мы можем

Б) Пусть в каждой клетке поля записано некоторое число. Требуется найти

В результате получим такую таблицу:

Последовательность из нулей и единиц без двух единиц подряд.

dp[i][j] – ответ для последовательности длины i, оканчивающейся на j
dp[1][0] =

Немного теории

Определения:
Состояние – это набор параметров, с помощью которых мы фиксируем

Чтобы успешно решить задачу динамикой нужно ответить на следующие вопросы:
1) Что

Порядок пересчёта

Существует три порядка пересчёта:
Прямой
Состояния последовательно пересчитываются исходя из уже посчитанных.

2) Обратный
Обновляются все состояния, зависящие от текущего состояния

3) Ленивая динамика
Рекурсивная функция пересчёта динамики. Это что-то вроде поиска в

Классы задач на ДП

Подсчёт объектов, в том числе определение существования объекта.

Виды задач на ДП

Линейное ДП
Многомерное ДП
ДП на подотрезках
ДП по полной сумме
ДП

Отдельно рассмотрим семейство задач о рюкзаке

Решение методом динамического программирования

Пусть dp[i][j] – есть максимальная стоимость предметов ,

Пример

W = 13, N = 5
w1 = 3, p1 = 1
w2

Другие задачи семейства

Ограниченный рюкзак - обобщение классической задачи, когда любой предмет

Решение методом ДП

Неограниченный рюкзак - обобщение ограниченного рюкзака, в котором любой предмет может

Пусть dp[i][j] – есть максимальная стоимость предметов , которое можно уложить

Непрерывный рюкзак - вариант задачи, в котором возможно брать любою дробную