Minimum Cost Path Problem in C++
This article will clarify the concept of the Minimum Cost Path Problem in C++ using Solutions with easy-to-understand examples. The Minimum Cost Path Problem is a decision-based problem to find the least total cost. In this problem, there is a matrix, and we return the minimum cost from the starting point to the end. Basically, these problem-based questions are asked in many interviews and by some popular online coding platforms like Leetcode, HackerRank, etc.
Minimum Cost Path Problem
Suppose we have a matrix and all the cells have a cost associated with it. After that, we have to return the minimum cost of reaching the destination cell (n-1, m-1) from the starting cell (0,0). From each cell, we can only traverse:
- 1 cell to the right side
- 1 cell to the downside
- 1 cell diagonally
Suppose, here is a cell given (i, j), cells (i+1, j), (i, j+1), and (i+1, j+1) can be traversed.
Problem
Here is given a 2D array of dimensions m x n. Each cell of the matrix has a cost. And we have to evaluate the minimum cost by reaching the last cell. i.e. cell with index (m-1) x (n-1) from the first cell i.e. (0) x (0) index.
The matrix path with minimum cost is shown in the following figure. Here is the path: (0, 0) >> (0, 1) >> (1, 2) >> (2, 2). The minimum total cost of the path is 8 (1 + 2 + 2 + 3).
After getting the minimum cost path of a given matrix, now we will try to solve the same problem using Recursion.
Min Cost Path Problem Solving Using Recursion
Consider the given suggestions to solve the given problem:
- This query contains the optimal substructure property. Here the path to access (m, n) must be passed over by one of the 3 cells: (p-1, q-1) or (p-1, q) or (p, q-1).
- Therefore, the minimum cost to reach the destination (p, q) can be denoted as min of the 3 cells + cost[p][q].
- MinCost(p, q) = min (MinCost(p-1, q-1), MinCost(p-1, q), MinCost(p, q-1)) + cost[m][n].
Now, follow the given below steps to solve the given query:
- If q and p is less than zero, then return Integer Maximum.
- If p and q is equal to zero, then return cost[p][q].
- Return cost[p][q] + minimum of (MinCost(p-1, q-1), MinCost(p-1, q), MinCost(p, q-1)).
Below is the code in C++ for the above implementing ideas:
#include <bits/stdc++.h>
using namespace std;
#define P 3
#define Q 3
int min(int x, int y, int z);
int minCost(int cost[P][Q], int p, int q)
{
if (q < 0 || p < 0)
return INT_MAX;
else if (p==0 && q==0)
return cost[p][q];
else
return cost[p][q]
+ min(minCost(cost, p - 1, q - 1),
minCost(cost, p - 1, q),
minCost(cost, p, q - 1));
}
int min(int x, int y, int z)
{
if (x < y)
return (x < z) ? x : z;
else
return (y < z) ? y : z;
}
int main()
{
int cost[P][Q]
= { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } };
cout << minCost(cost, 2, 2) << endl;
return 0;
}
Output:
Time Complexity: O((p*q)3
Auxiliary Space: O(p+q)
Now, move to discuss another popular method to solve min cost path problems with a C++ example.
Min Cost Path Using Memoization
The recursive method is not enough for large values. Also, its time complexity is exponential with the number of turns (i.e. time complexity O(2N).- Using the recursive function, we can recompute the same thing multiple times. On the other side, the Memoization method saves the results of the sub-problems into a table. The recursive method can do only up to N=24. Here is a dynamic programming-based solution for the MCP problem.
#include <bits/stdc++.h>
using namespace std;
#define P 3
#define Q 3
int min(int a, int b, int c);
int minCostMemoized(int cost[P][Q], int p, int q,
int memo[P][Q])
{
if (q < 0 || p < 0)
return INT_MAX;
else if (p == 0 && q == 0)
return cost[p][q];
if (memo[p][q] != -1)
return memo[p][q];
memo[p][q]
= cost[p][q]
+ min(minCostMemoized(cost, p - 1, q - 1, memo),
minCostMemoized(cost, p - 1, q, memo),
minCostMemoized(cost, p, q - 1, memo));
return memo[p][q];
}
int minCost(int cost[P][Q], int p, int q)
{
int memo[P][Q];
memset(memo, -1,
sizeof(memo));
return minCostMemoized(cost, p, q, memo);
}
int min(int a, int b, int c)
{
if (a < b)
return (a< c) ? a : c;
else
return (b < c) ? b : c;
}
int main()
{
int cost[P][Q]
= { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } };
cout << minCost(cost, 2, 2) << endl;
return 0;
}
Output: