Finding Minimum Cost Path in a 2-D Matrix in C++

In this tutorial, we are going to solve a particular problem which is how to find Minimum Cost Path in a 2-D Matrix in C++. We are going to use dynamic programming to solve this problem.

A cost matrix will be given to us, using this we have to calculate the minimum cost.

Consider the following cost matrix :

1 2 3

5 7 2

1 5 2

Minimum cost path to reach from (0,0) to (2,2) is (0, 0) >> (0, 1) >>  (1, 2) >> (2, 2) and the cost will be 7.

It is very easy to note that if we reach a position (i,j) in the grid, we must have come from one cell higher, i.e. (i-1,j) or from one cell to our left, i.e. (i,j-1) or diagonal cell which is(i-,j-1). Iy means that the cost of visiting cell (i,j) will come from the following recurrence relation:

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

The problem of finding the minimum cost Path is now almost solved. Now we will compute the values of the base cases: the topmost row and the leftmost column. For the topmost row, a cell can be reached only from the cell on the left of it. Assuming 0 based index,

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

Similarly:

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

Let’s try to implement our idea in our code to get the required solution.

Program to Find Minimum Cost Path in a 2-D Matrix in C++

Cpp source code:

// Program for Finding Minimum Cost Path in a 2-D Matrix
#include<bits/stdc++.h>
using namespace std;
 
int minCost(int cost[100][100],int m,int n)
{
    int i, j;
    int dp[100][100];   
  
    dp[0][0] = cost[0][0]; 
  
     
    for (i = 1; i <= m; i++) 
    {
       dp[i][0] = dp[i-1][0] + cost[i][0];
    } 
    for (j = 1; j <= n; j++) 
    {
       dp[0][j] = dp[0][j-1] + cost[0][j];
    } 
    for (i = 1; i <= m; i++) 
    {
       for (j = 1; j <= n; j++)
       {
          dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + cost[i][j];
       }
    }
    return dp[m][n];
}

// Driver Code
int main()
{	
  int cost[100][100] ={ 
                      {1, 2, 3},
                      {5, 7, 2},
                      {1, 5, 2} };
  cout<<"\nMinimum cost: "<<minCost(cost,2,2)<<"\n";
  return 0;
}

Input:

1 2 3
5 7 2
1 5 2

Output:

Minimum cost: 7

You may also learn:

Rotate a Matrix in C++ ( Clockwise and Anticlockwise )

Travelling Salesperson Problem using Dynamic Approach in C++

Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.

One response to “Finding Minimum Cost Path in a 2-D Matrix in C++”

1. Ashwin says:

   July 3, 2021 at 3:52 pm

   But how do u print the path, thats the twist

   Reply