Задача динамического программирования для минимизации затрат при создании неубывающего массива

Question

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

Алгоритм, который я создаю, получает массив целых чисел, {y_1... y_n} и параметр M, и должны возвращать неубывающий массив целых чисел {x_1 ... x_n}, где никакие значения не больше, чем M в любом массиве, или меньше 0. Это должно быть сделано для минимизациисумма ({X_i - Y_i} ^ 2).

Как видите, это не простая проблема, которую можно жадно решить.Решение должно быть в O (нМ) времени.

Answer 1

Заполняем таблицу Cost(i, j), где i in {1, ..., n} и j in {0, ..., M}.Интерпретация Cost(i, j) состоит в том, что это минимальная стоимость для подзадачи y_1, ..., y_i с пределом j, где x_i = j (некоторые значения y могут быть больше, чем j, но проблема все еще можетбыть четко определенным).У нас есть рецидивы для всех i in {2, ..., n} и всех j in {0, ..., M},

                      2
Cost(1, j) = |j - y_i|
                                             2
Cost(i, j) =   min   Cost(i-1, k) + |j - y_i|
             0<=k<=j

Наивно, это фактор M слишком медленный.Однако, если мы оценим Cost в правильном порядке, мы можем заменить min на min предыдущего минимума и Cost(i-1, j) и получить желаемое время работы O(n M).