Given a M x N matrix where each cell has a cost associated with it, find the minimum cost to reach last cell (M-1, N-1) of the matrix from its first cell (0, 0). We can only move one unit right or one unit down from any cell. i.e. from cell (i, j), we can move to (i, j+1) or (i+1, j).

The highlighted path shows the minimum cost path having cost of 36.

The idea is to use recursion. The problem has an optimal substructure. That means the problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial. The problem can be recursively defined as –

Cost to reach cell (m, n) = cost[m][n] + min (cost to reach cell (m, n-1),

cost to reach cell (m, n-1))

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <bits/stdc++.h> using namespace std; // M x N matrix #define M 5 #define N 5 // Naive recursive function to find the minimum cost to reach // cell (m, n) from cell (0, 0) int findMinCost(int cost[M][N], int m, int n) { // base case if (n == 0 || m == 0) return INT_MAX; // if we're at first cell (0, 0) if (m == 1 && n == 1) return cost[0][0]; // include cost of the current cell in path and recuse to find minimum // of the path from adjacent left cell and adjacent top cell. return min (findMinCost(cost, m - 1, n), findMinCost(cost, m, n - 1)) + cost[m - 1][n - 1]; } // main function int main() { int cost[M][N] = { { 4, 7, 8, 6, 4 }, { 6, 7, 3, 9, 2 }, { 3, 8, 1, 2, 4 }, { 7, 1, 7, 3, 7 }, { 2, 9, 8, 9, 3 } }; cout << "The minimum cost is " << findMinCost(cost, M, N); return 0; } |

`Output:`

The minimum cost is 36

The time complexity of above solution is exponential as we’re doing a lot of redundant work. For example, consider the recursion tree for a 5 x 5 matrix.

As we can see, the same sub-problems (highlighted in same color) are getting computed again and again. As the recursion grows deeper, more and more of this type of unnecessary repetition occurs. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are memoized rather than computed again and again. Now each time we compute the minimum cost of reaching any cell (i, j), we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it.

The following bottom-up approach computes, for each 0 <= i < M and 0 <= j < N, the minimum costs of reaching cell (i, j) from cell (0, 0), using the costs of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <bits/stdc++.h> using namespace std; // M x N matrix #define M 5 #define N 5 // Iterative function to find the minimum cost to traverse from the // first cell to last cell of a matrix int findMinCost(int cost[M][N]) { // T[i][j] maintains minimum cost to reach cell (i, j) from cell (0, 0) int T[M][N]; // fill matrix in bottom-up manner for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { T[i][j] = cost[i][j]; // fill first row (there is only one way to reach any cell in // the first row, that is from its adjacent left cell) if (i == 0 && j > 0) T[0][j] += T[0][j - 1]; // fill first column (there is only one way to reach any cell // in the first column, that is from its adjacent top cell) else if (j == 0 && i > 0) T[i][0] += T[i - 1][0]; // fill rest of the matrix (there are two way to reach any cell // in the rest of the matrix, that is from its adjacent left // cell or adjacent top cell) else if (i > 0 && j > 0) T[i][j] += min(T[i - 1][j], T[i][j - 1]); } } // last cell of T[][] stores min cost to reach destination cell // (M-1, N-1) from source cell (0, 0) return T[M - 1][N - 1]; } // main function int main() { int cost[M][N] = { { 4, 7, 8, 6, 4 }, { 6, 7, 3, 9, 2 }, { 3, 8, 1, 2, 4 }, { 7, 1, 7, 3, 7 }, { 2, 9, 8, 9, 3 } }; cout << "The minimum cost is " << findMinCost(cost); return 0; } |

`Output:`

The minimum cost is 36

The time complexity of above solution is O(M x N) and auxiliary space used by the program is O(M x N).

**Exercise:** Extend the solution to consider diagonal moves as well.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply