This is really an interesting problem, and I used an algorithm similar to Bellman-Ford to solve it. It seems not related to the 1-D problem but in fact there is some common point but the 1D problem is to easy so we ignored the thinking and optimizing process to get the best greedy strategy directly.

After solving this problem, I come up an follow up, it is straightforward that what if the given height map is 3D and is able to go in 8 direction?