Невозможно Понять динамическое программирование

Question

Я имел задание на динамическое программирование из-за прошлой ночью, но я должен был превратить его в незаконченном, потому что я не мог понять, как решить последнюю проблему:

Государство хочет контролировать движение по шоссе длиной в три мили. Это стоит c _i для установки устройства мониторинга на миле i шоссе. Максимальное расстояние между контрольными устройствами не должно превышать d миль. То есть, если на миле i есть контрольное устройство, то должно быть одно контрольное устройство от мили i + 1 до мили i + d (или в этом случае i + d> n). Государству нужен план, который минимизирует стоимость. Предположим, что существует массив C [1..n] затрат.

Пусть v _k будет стоить лучшего решения, предполагающего шоссе на километр и предполагая устройство мониторинга на милю k. С учетом C и d, если известны значения v по v _k-1, показать, как определить значение v _k. Вы можете написать это математически или предоставить псевдокод в стиле книги. Заметим, что вам нужно учитывать все возможные значения k от k = 1 до k = n.

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

Answer 1

Определим DP [I] в качестве минимальной стоимости установки монитора на станции я и некоторые другие показатели, которые меньше, чем я (таким образом, что каждая последующая станция меньше или равно расстоянию г)

Теперь ответ на нашу проблему будет

мин (DP [п - d + 1], ... DP [п - 2], DP [п - 1], DP [п])

То есть минимальная стоимость последнего монитора для последних индексов d.

Теперь, рекуррентное соотношение для динамического программирования можно легко увидеть, как:

DP [I] = мин (DP [I - 1], DP [I - 2], ... DP [I - d]) + C [i] Если мы хотим установить монитор на i-й индекс, мы устанавливаем его по цене C [i], и мы также должны убедиться, что у нас есть монитор в предыдущих индексах d. Итак, мы берем минимум установки второго последнего монитора на предыдущие индексы d.

Если вы кодируете повторение по методу наивности, то он выглядит O (n * d), но, используя минимальный алгоритм скольжения, используя двойную очередь, вы можете уменьшить временную сложность до асимптотически O (n).

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