Minimum cost path in grid
Problem statement is : Given a 2D matrix, Cost, where Cost[i][j] represent the cost of visit cell Cost[i][j], find minimum cost path to reach a given cell Cost[n][m], where a cell can be reach from it’s left (by moving one step right) or from top (by moving one step down).
Finding Minimum Cost Path in a 2D Matrix
This problem is very similar to what we saw in Finding possible paths in grid. As mentioned there, grid problem reduces to smaller subproblems one we make a choice at a cell. In this problem, to reach a cell (i,j), we can either come from cell ( i-1, j ) from the top, or from cell (i, j-1) from left, whichever is minimum.
CostToMove(i,j) = Min(CostToMove(i-1,j), CostToMove (i, j-1)) + Cost(i,j)
This equation gives hint at recursion. What should be terminating condition for recursion. It’s obvious, when we reach desired cell.
findCost(i,j, cost) = cost(i,j) + Min( findCost(i-1,j, cost), findCost(i,j-1, cost))
Recursive implementation of recursion equation to find minimum cost to reach a given cell in matrix.
Complexity of recursive method is exponential.
Notice that this problem satisfies two basic conditions to apply dynamic programming.
Optimal Sub-structure:- Optimal solution to bigger problem involves optimal solutions to subproblems.
Overlapping Subproblems:- Subproblems once computed can be stored in a table for further use. This saves the time needed to compute the same sub-problems again and again.
To find more about these properties, please refer : Dynamic programming basics.
Solution to this problem depends on solution to subproblems and we can see that there are many subproblems which are calculated again and again. So, this problem is ideal candidate for applying dynamic programming.
Let’s create a two dimensional matrix and fill it up bottom up. Let’s consider the top most row in matrix. Any cell in top most row can be reach only from left.
MinCost(0,j) = MinCost(0,j-1) + Cost[j]
Similarly, cell in leftmost column can only be reached from top.
MinCost(i,0) = MinCost(i-1,0) + Cost[i]
For all other cells,
MinCost(i,j) = Min( MinCost(i-1),j), MinCost(i, j-1)) + Cost[i][j]
Implementation of minimum cost path using dynamic programming
Complexity of dynamic programming approach to find minimum cost path in grid is O(n2) with additional space complexity of O(n2).
There is extension to the problem which is to find actual path that lead to the destination. Solution is simple, start from the destination cell, as that will be part of path anyways, start moving either to cell to left or top whichever is minimum till you reach origin cell.
There is one more variant of this problem, when we can move from left to right, top to down and diagonally as well. Nothing changes in solution except that we need to take minimum of three cells (left, top and diagonal).