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

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) .