动态规划问题，用于最小化创建非递减数组的成本

Question

这个问题我已经有一段时间需要解决，但一直想不出使用动态编程解决这个问题的有效方法。

我正在创建的算法被赋予了一个整数数组，{y_1 ...y_n} 和参数 M，并且必须返回一个非递减的整数数组 {x_1 ...x_n}，其中任一数组中没有大于 M 或小于 0 的值。必须这样做以最小化总和({X_i - Y_i}^2)。

如您所见，这不是一个可以贪婪解决的简单问题。解决方案必须在 O(nM) 时间内。

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，我们可以将最小值替换为前一分钟和Cost(i-1, j)的最小值，并获得所需的运行时间O(n M).