Finding optimal path (if exists)

Question

Given the parameter k and an array [a₀, a₁, a₂, a₃, ..., a_n], where a_x defines the height of the terrain, find the least amount of work you need to make the terrain passable. The terrain is passable that if the difference between two neighbouring places is smaller or equal to k. The height of the terrain at a_x can be changed and the amount of work needed is equal to the difference in height you make. The height of a₀ and a_n can't be changed and therefore some terrains may be completely unpassable.

I've been struggling with this for a while: This is what I figured out so far: Of course finding a solution (not taking the least amount of work needed into account) is easy - make 'steps' from a₀ to a_n as in the diagram with k = 2 (red dots are the heights of the old terrain, grey for the new).

(The input for this particular terrain would be: k = 2, [0, 2, 3, 2, 5, 4, 5, 7])

As you can see, the new terrain doesn't take the old terrain into account and thus the work needed to transform the old one into this one can be huge.

Determining whether a path exists is trivial: k >= |a₀-a_n|/n, but I have no idea about how would I go around in finding the optimal solution.

Answer 1

Use the simplex method to solve the following linear program.

minimize sum_i y_i
subject to
# y_i is notionally |x_i - a_i|
# equality holds in every optimal solution
y_i >= x_i - a_i for all i
y_i >= a_i - x_i for all i
# transformed terrain is passable, i.e., |x_i - x_{i+1}| <= k
x_i - x_{i+1} <= k for all i
x_{i+1} - x_i <= k for all i