Minimum cost path in matrix : Dynamic programming

Minimum cost path in matrix : Dynamic programming

Given a 2D matrix, Cost[][], where Cost[i][j] represent cost of visiting cell (i,j), find minimum cost path to reach cell (n,m), where any cell can be reach from it’s left (by moving one step right) or from top (by moving one step down).
For example, to reach (3,3) would be 16 by following path = ((0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3))

minimum cost path in matrix

Minimum cost path : line of thoughts

This problem is similar to Finding possible paths in grid. As mentioned there, grid problem reduces to smaller sub-problems once choice at the cell is made, but here move will be in reverse direction. To find minimum cost at cell (i,j), first find the minimum cost to the cell (i-1, j) and cell (i, j-1). Take the minimum of those two and add the cost of the cell (i,j) which will be the minimum cost to reach (i,j).
Solution(n) = Cost of choice + Solution(n-1).

CostToMove(i,j) = Min(CostToMove(i-1,j), CostToMove (i, j-1)) 
                       + Cost(i,j)

Above equation can be implemented in recursive function. What should be terminating condition for recursion? It’s obvious, at starting cell i.e i=0 and j=0.

findCost(i,j, cost) = cost(i,j) + Min( findCost(i-1,j, cost),
                                       findCost(i,j-1, cost))

Minimum cost path in matrix : Recursive implementation:

#include <stdio.h>
#include <stdlib.h>

int min( int a, int b){
    if(a > b) return b;
    return a;
}

int findMinimumCostPath(int Cost[3][3], int i, int j){
	
    if( i == 0 && j == 0 )
        return Cost[0][0];
	
    if( i == 0 )
	return findMinimumCostPath(Cost,i, j-1)
               + Cost[i][j];
    if( j == 0) 
    	return findMinimumCostPath(Cost,i-1, j)
               + Cost[i][j];
    	
    return min(findMinimumCostPath(Cost,i-1, j), 
    		   findMinimumCostPath(Cost,i, j-1)
                   + Cost[i][j]);
}
int main()
{
    int M,N; 
    
    M = N = 3; 
    int Cost[3][3] = {
        1,3,4,
    	5,3,2,
        3,4,5
    };
    printf("Minimum cost of path : %d" ,
         findMinimumCostPath(Cost, M-1, N-1));
    
}

Another way to implement the same function in Java

    private int minPathSumUtilRec(int[][] grid, int i, int j){
        
        int m = grid.length;
        int n = grid[0].length;
        
        if(i>m-1 || j > n-1 ){
            return Integer.MAX_VALUE;
        }
        
        if(i == m-1 && j == n-1 ) 
            return grid[i][j];
    
        return Math.min(minPathSumUtilRec(grid, i+1, j), 
                        minPathSumUtilRec(grid, i, j+1)) + grid[i][j];
        
    }

This solution exceeds the time limit on leet code submission for Minimum cost path in the matrix, because we are following each possible path. The number of paths in the matrix with given conditions is exponential and hence, the complexity of the recursive method is exponential too. Can we do better than that?

We saw that the problem reduces to subproblem at every cell and optimal solution to a bigger problem depends on the optimal solution of subproblem, which is known as optimal sub-structure. This is one of the conditions to apply dynamic programming.

There are several subproblems which are solved again and again in recursive solution i.e there are overlapping subproblems. How can we avoid re-solving subproblems? First immediate thing we can do it to store the result of already solved problems and use them when required. Below implementation uses a two-dimensional table to store the minimum cost to reach cell(i,j) and uses it when we have to solve the problem for cell (i,j).

    //Top down approach
    private int minPathSumUtilTopDown(int[][] grid, int i, int j, int[][] table){
        
        int m = grid.length;
        int n = grid[0].length;
        
        if(i>m-1 || j > n-1 ){
            return Integer.MAX_VALUE;
        }
        
        if(i == m-1 && j == n-1 ) 
            return grid[i][j];
        
        //If solution is already present, return it
        if(table[i][j] < Integer.MAX_VALUE) return table[i][j];
    
        table[i][j] = Math.min(minPathSumUtilTopDown(grid, i+1, j, table), 
                      minPathSumUtilTopDown(grid, i, j+1, table))
             + grid[i][j];
        
        return table[i][j];
        
    }

Above solution falls within time limit when tested on leetcode.

Another approach is to use the bottom-up approach when we start with a solution to the smaller problem and try to find a solution to the bigger problem. Create a 2-dimensional array to save solutions of subproblem. Each cell M[i][j] will store the minimum cost path until cell (i,j).
Top most row in array is peculiar as any cell in that row can be reached only from left cell.

MinCost(0,j) = MinCost(0,j-1) + Cost[0][j]

Similarly, cell in leftmost column can only be reached from top cell.

MinCost(i,0) = MinCost(i-1,0) + Cost[i][0]

For all other cells,

MinCost(i,j) = Min( MinCost(i-1),j), MinCost(i, j-1)) + Cost[i][j]

Since, the solution of (i-1, j) and (i, j-1) is prerequisite for the solution of (i,j), this filling method is called bottom up.

Minimum cost path in matrix : Dynamic programming implementation

#include <stdio.h>
#include <stdlib.h>

int min( int a, int b){
    if(a > b) return b;
    return a;
}

int findMinimumCostPath(int Cost[3][3], int M, int N){
    //declare the minCost matrix	
    int MinCost[M][N]; 

    MinCost[0][0] = Cost[0][0];

    // initialize first row of MinCost matrix
    for (int i=1; i<N; i++){
        MinCost[0][i] = MinCost[0][i-1] + Cost[0][i];
    }

    for (int i=1; i<M; i++){
        MinCost[i][0] = MinCost[i-1][0] + Cost[i][0];
    }
    
    for (int i=1;i<M; i++){
    	for (int j=1; j<N; j++){
           MinCost[i][j] = min(MinCost[i-1][j],
                           MinCost[i][j-1]) + Cost[i][j];
        }
    }

    return MinCost[M-1][N-1];
    
}
int main()
{
    int M,N; 
    M = N = 3; 
    int Cost[3][3] = {
    	1,3,4,
    	5,3,2,
    	3,4,5
    };
    printf("Minimum cost of path : %d" ,
            findMinimumCostPath(Cost, M, N));
    
}

Complexity of dynamic programming approach to find minimum cost path in grid is O(n2) with additional space complexity of O(n2).

Extend this problem by actually finding a path that leads to the destination. The solution is simple, start from destination cell, as that will be part of final path anyways, start moving either to a cell to left or top of the cell, whichever is less till you reach origin cell.

One more variant of this problem is adding flexibility that one can move from left to right, top to down and diagonally as well. Nothing changes in solution except take a minimum of three cells instead of two (left, top and diagonal).

Please share if there is something wrong or missing. If you want to contribute, please write to us