Привет, ребята: у меня интересный вопрос, который меня некоторое время озадачивает. Это упражнение по динамическому программированию в книге «Введение в алгоритм».
Телефонная компания, в которой вы работаете, недавно приобрела услуги телефонной связи в новом городе. Вы были специально назначены для работы на телефонных столбах на Главной улице. В ряду от 1 до N находятся N полюсов, а полюс i имеет высоту H [i] футов, которая является целым числом в диапазоне [1, maxH]. Город попросил вас сделать все столбы одинаковой высоты. Для каждого i, если i-й полюс имеет высоту h, а (i-1) -ый полюс имеет высоту h ′, то вы должны заплатить налог C | h − h ′ |. Чтобы помочь в достижении этой цели, вы можете увеличить высоту или уменьшить высоту любого полюса до высоты h со стоимостью (H [i] −h) ^ 2. Ваша задача - решить, как увеличить или уменьшить высоту каждого полюса, чтобы ваша компания потратила наименьшее количество денег. В частности, вы должны сбалансировать стоимость изменения высоты полюсов с налогом, который ваша компания должна будет заплатить.
(Подсказка) вы должны по крайней мере сделать это за O (NH ^ 2), но лучшее, что вы можете сделать, это на самом деле O (HN).
Пока у меня есть O (NH ^ 2). Моя идея состоит в том, что мы инициализируем матрицу M размером HxN, каждая запись M [h, i] представляет минимальную стоимость для первых полюсов i с высотой i полюса h. Моя цель состоит в том, чтобы заполнить всю матрицу и изучить последний столбец, а именно определить последний полюс, высота которого будет иметь глобальную минимальную стоимость для нашей задачи.
def DP_pole(H,hmax,C,N):
initialize empty matrix M[H,N]
for i from 1 to hmax: #first pole,no tax, only construction fee
M[i,1] = (H[1] - i)**2
for n from 2 to n: #column first
for h from 1 to hmax: #row second
construction = (H[n]-h)**2 # you pay this construction always
minimum = min(M[1,n-1]+C|h-1|,......,M[hmax,n-1]+C|h-hmax|)
M[h,n] = construction + minimum
#------find minimum------#
min = float("-inf")
for h from 1 to hmax:
if M[h,N] < min:
min = M[h,N]
return min
Но алгоритм, который я до сих пор получил, не можетбыть уменьшенным до O (HN), я думаю (возможно?). Поскольку рекуррентное отношение, которое я использую, является «линейным», чтобы определить каждую запись матрицы H, я пойду искать весь предыдущий столбец, который принимает O (H). Всего в матрице должно быть заполнено H * N записей.
Будем весьма благодарны за любые подсказки или помощь. Нужно ли придумывать другое, более умное отношение повторения?
Спасибо за ваше время.