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

1. If q and p is less than zero, then return Integer Maximum.
2. If p and q is equal to zero, then return cost[p][q].
3. 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 3int 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];elsereturn 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 3int 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: