我已经有一段时间要解决这个问题，但一直无法想出一种使用动态编程来解决这个问题的有效方法。
我正在创建的算法被赋予一个整数数组 {y_1 ... y_n} 和一个参数 M，并且必须返回一个非递减的整数数组 {x_1 ... x_n}，其中没有值大于 M要么是数组，要么是小于 0。必须这样做以最小化总和（{X_i - Y_i}^2）。
如您所见，这不是一个可以贪婪解决的简单问题。解决方案必须在 O(nM) 时间内。
我们填写表格Cost(i, j)wherei in {1, ..., n}和j in {0, ..., M}。的解释Cost(i, j)是它是y_1, ..., y_i具有限制的子问题的最小成本jwhere 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 替换 minCost(i-1, j)并获得所需的运行时间O(n M)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句