Minimum cost path in matrix

Tags: , , , ,

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

Minimum cost path : line of thoughts

This problem is similar to Finding possible paths in grid. As mentioned there, the grid problem reduces to smaller sub-problems once choice at the cell is made, but here move will be in the 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)

The above equation can be implemented in recursive function. What should be the 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))

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 the 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? The 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 using cache

    //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];
        
    }

The above solution falls within the 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).

Topmost row in the array is peculiar as any cell in that row can be reached only from the left cell.

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

Similarly, cells in the leftmost column can only be reached from the 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 a prerequisite for the solution of (i,j), this filling method is called bottom-up.

Minimum cost path: 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];
    
}

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 the 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