Cheapest way to move through an array

Question

I have a n x n array. Each field has a cost associated with it (a natural number) and I here's my problem:

I start in the first column. I need to find the cheapest way to move through an array (from any field in the first column to any in the last column) following these two rules:

I can only make moves to the right, to the top right, the lower right an to the bottom.
In a path I can only make k (some constant) moves to the bottom.

Meaning when I'm at cell x I can moves to these cells o:

enter image description here

How do I find the cheapest way to move through an array? I thought of this:

-For each field of the n x n array I keep a helpful array of how many bottom moves it takes to get there in the cheapest path. For the first column it's all 0's.

-We go through each of the field in this orded : columns left to right and rows top to bottom.

-For each field we check which of their neighbours is 'the cheapest'. If it's the upper one (meaning we have to take a bottom route to get from him) we check if it took k bottom moves to get to him, if not then then we assign the cost of getting to analyzed field as the sum of getting to field at the top+cost of the field, and in the auxilary array for the record corresponding to the field the put the number of bottom moves as x+1, where x is how many bottom moves we took to get to his upper neightbour.

-If the upper neighbour is not the cheapest we assign the cost of the other cheapest neighbour and the number of bottom moves as the number of moves we took to get to him.

Time complexity is O(n^2), and so is memory.

Is this correct?

Go from any field in the first column to any field in the last column. — Arek Krawczyk, Jun 09 '14 at 13:21
Since the possible moves form an acyclic graph, DP is possible. Let f(i,j) be the shortest path to get from any field in the first column to the field (i,j). We have f(i,0) = 0 and f(i,j) = min { f(i-1,j), f(i+1, j-1), f(i, j-1), f(i-1, j-1) } — Niklas B., Jun 09 '14 at 13:46
@ArekKrawczyk I didn't see that, but you can add an extra DP parameter for that. f(i,j,k) is the shortest path from the first column to (i,j) with at most k downward moves. The resulting algorithm has complexity O(n^2 * k) — Niklas B., Jun 09 '14 at 13:51
Why is my approach wrong? With keeping how many moves downward we made to the field along with the field? — Arek Krawczyk, Jun 09 '14 at 13:57
@ArekKrawczyk Because the cost is dependent on the number of downward moves you make. — Niklas B., Jun 09 '14 at 14:00
use A* or Djikstra's Algorithm (http://stackoverflow.com/a/23779490/2521214) but change the neighbouring conditions/fill to match your need and fill map with the lowest cumulative cost instead of path length. — Spektre, Jun 09 '14 at 14:51
@Spektre Shortest path on DAGs can be solved in linear time, no need for Dijkstra — Niklas B., Jun 09 '14 at 14:55

Vikram Bhat · Answer 1 · 2014-06-10T09:38:28.127

Here is DP solution in O(N^2) time and O(N) memory :-

Dist(i,j) = distance from point(i,j) to last column.

Dist(i,j) = cost(i,j) + min { Dist(i+1,j),Dist(i,j+1),Dist(i+1,j+1),Dist(i-1,j+1) }

Dist(i,N) = cost[i][N]

Cheapest = min { D(i,0) } i in (1,M)

This DP equation suggests that you need only values of next rows to get current row so O(N) space for maintaining previous calculation. It also suggests that higher row values in same column need to evaluated first.

Pseudo Code :-

int Prev[N],int Curr[N];

// last row calculation => Base Case for DP

 for(i=0;i<M;i++) 
   Prev[i]  = cost[i][N-1];

// Evaluate the rows and columns in descending manner 

for(j=N-2;j>=0;j--) {

 for(i=M-1;i>=0;i--) {

    Curr[i][j] = cost[i][j] + min ( Curr[i+1][j],Prev[i][j+1],Prev[i-1][j+1],Prev[i+1][j+1] )
 }

 Prev  = Curr

}

// find row with cheapest cost
Cheapest = min(Prev)

Cheapest way to move through an array

1 Answers1