# 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[j]`

Similarly:

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

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,int m,int n)
{
int i, j;
int dp;

dp = cost;

for (i = 1; i <= m; i++)
{
dp[i] = dp[i-1] + cost[i];
}
for (j = 1; j <= n; j++)
{
dp[j] = dp[j-1] + cost[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 ={
{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:

But how do u print the path, thats the twist