# Minimum Cost Path

## Minimum Cost Path

In the Minimum Cost Path problem, we are given a matrix and we have to return the minimum cost from starting point to the destination. In this article, we will provide C++ Solution with an explanation of the problem. ## Minimum Cost Path Problem Description

We are given a n*m matrix. Each cell of the matrix has a cost associated to it. We have to return the minimum cost of reaching the destination (n-1,m-1) from the staring cell (0,0).

From any cell we can,

• Move 1 cell right.
• Move 1 cell down.
• Move 1 cell down diagonally.

Input:

• First line contains 2 integers n & m – The dimensions of matrix.
• Next n lines contain m integers each specifying the cost associated with each cell.

Output:

Cost of Minimum Possible Path.

## Minimum Cost Path Problem Solution Explanation

### Solution (Top Down):

To build a top-down solution we must follow the following steps –

• Break Down the Problem – Let’s suppose we have a function – F(i,j) = Minimum cost of path from (0,0) to(i,j).

For finding F(i,j) we require the cost of (we will take a minimum of all these options)-

F(i-1,j) ie one cell up

F(i,j-1) ie one cell left

F(i-1,j-1) ie one cell upwards but diagonally.

Thus, F(i,j) = cost(i,j) + min({F(i-1,j-1), F(i-1,j),F(i,j-1)})

• Find the base case – The base case is the solution to the smallest known problem. Here F(0,0) ie cost of (0,0) to (0,0) is cost(0,0). Also, we need to keep a check on whether we are inside the grid or not. If we move outside we return a very large value to penalize the result.
• Check for optimal substructure and overlapping subproblems – It is easy to see that the problem can be broken down into smaller problems. The optimal substructure and overlapping subproblems properties can be visualized below. ### Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
#define inf 100000000
int memo[N][N];
int mat[N][N];
int nm;
int f(int iint j)
{
if (i < 0 || i >= n) // If we move out of matrix
return inf;
if (j < 0 || j >= m)
return inf;
if (i == 0 && j == 0)
{
return mat[i][j];
}

if (memo[i][j] != –1)
return memo[i][j];

int op1 = mat[i][j] + f(i – 1j – 1); // Moving Diagonally
int op2 = mat[i][j] + f(i – 1j);     // Moving Up
int op3 = mat[i][j] + f(ij – 1);     // Moving Down

// Taking minimum of all options
return memo[i][j] = min(op1min(op2op3));
}
int main()
{
cin >> n >> m;

for (int i = 0i < ni++)
{
for (int j = 0j < mj++)
{
cin >> mat[i][j];
}
}
memset(memo, –1, sizeof memo);
cout << f(n – 1m – 1<< endl;
cout << f2() << endl;

return 0;
}

### Output

`3 31 2 34 5 67 8 915`

### Bottom up Solution

Here we create a dp table and where dp[i][j] = minimum cost of path from (0,0) to (i,j).

Now we just have to use same transitions as above. Refer to code for more detail.

### Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
#define inf 100000000
int dp[N][N];
int mat[N][N];
int nm;
int f()
{
for (int i = 1i <= ni++)
{
for (int j = 1j <= mj++)
{
dp[i][j] = mat[i – 1][j – 1] + min(dp[i – 1][j], min(dp[i – 1][j – 1], dp[i][j – 1]));
}
}
return dp[n][m];
}
int main()
{
cin >> n >> m;

for (int i = 0i < ni++)
{
for (int j = 0j < mj++)
{
cin >> mat[i][j];
}
}
cout<<f()<<endl;

return 0;
}

### Output

`3 31 2 34 5 67 8 915`