CODEWITHSUNDEEP
arraysalgorithmdynamicdifferenceminimize
quackingplatypus
quackingplatypus

Reputation: 103

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

I have had this problem to solve for a while and have been unable to think of an efficient way to solve this using dynamic programming.

The algorithm I am creating is given an array of integers, {y_1 ... y_n} and a parameter M, and must return a non-decreasing array of integers {x_1 ... x_n}, where no values are greater than M in either array, or less than 0. This must be done to minimize the sum({X_i - Y_i}^2).

As you can see this is not a straightforward problem that can be solved greedily. The solution must be in O(nM) time.

Upvotes: 2

Views: 869

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

We fill in a table Cost(i, j) where i in {1, ..., n} and j in {0, ..., M}. The interpretation of Cost(i, j) is that it's the min cost for the sub-problem y_1, ..., y_i with limit j where x_i = j (some of the y values may be greater than j, but the problem can still be well defined). We have a recurrence for all i in {2, ..., n} and all 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

Naively, this is a factor of M too slow. If we evaluate Cost in the right order, however, we can replace the min with the min of the previous min and Cost(i-1, j) and get the desired running time of O(n M).

Upvotes: 1

Related Questions