Дома на длинной улице необходимо контролировать в целях безопасности. В каждом доме может быть установлен датчик безопасности, но его стоимость варьируется от дома к дому. Стоимость добавления датчика в дом - это ci, где все значения ci положительны.
Для покрытия улицы не может быть более 2 последовательных домов без датчика, а также первого и последнего домов. должны иметь датчики. Мы хотим минимизировать общую стоимость установки датчиков.
(a) Разработать и написать алгоритм динамического программирования, который, учитывая количество домов и стоимость каждого датчика, найдет минимальную общую стоимость установки. датчики для покрытия улицы.
(b) Асимптотически проанализируйте ваш алгоритм из (a).
(c) Адаптируйте свой алгоритм из (a), чтобы найти набор домов для установки датчиков наэто производит минимальную стоимость.