Minimum Cost Path

November 6, 2021

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

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.
Minimum Cost Path Sub Problems

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
#define inf 100000000
int memo[N][N];
int mat[N][N];
int n, m;
int f(int i, int 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 – 1, j – 1); // Moving Diagonally
    int op2 = mat[i][j] + f(i – 1, j);     // Moving Up
    int op3 = mat[i][j] + f(i, j – 1);     // Moving Down

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

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

    return 0;
}

Output

3 3
1 2 3
4 5 6
7 8 9
15

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 n, m;
int f()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            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 = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> mat[i][j];
        }
    }
    cout<<f()<<endl;

    return 0;
}

Output

3 3
1 2 3
4 5 6
7 8 9
15