# 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.

## Leave a Reply