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

Question

这个问题我已经解决了一段时间了，一直想不出一个有效的方法来使用动态规划来解决这个问题。

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

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

Answer 1

我们填一个tableCost(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)。

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

Dynamic Programming Problem to Minimize Cost in Creating a non-decreasing array

arrays

algorithm

dynamic

difference

minimize