Given a M x N matrix where each cell have non-negative cost associated with it, count number of paths to reach last cell (M-1, N-1) of the matrix from its first cell (0, 0) such that path has given cost. 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).

For example, consider below 4 x 4 matrix where cost is 25. There are two paths having cost of 25.

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 –

path(m, n, cost) = path(m, n – 1, cost – M[m][n]) (if m == 0)

= path(m – 1, n, cost – M[m][n]) (if n == 0)

= path(m – 1, n, cost – M[m][n])

+ path(m, n – 1, cost – M[m][n]) (otherwise)

path(0, 0, cost) = 1 (if M[m][n] == cost)

= 0 (otherwise)

Here, path(m, n, cost) represents the total number of paths to reach cell (m, n) from cell (0, 0) of matrix M and each path have cost cost.

**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 |
#include <bits/stdc++.h> using namespace std; // M x N matrix #define M 4 #define N 4 // Naive recursive top-down function to count total number of paths // to reach cell (m, n) from cell (0, 0) and having given cost int countPaths(int mat[][N], int m, int n, int cost) { // base case if (cost < 0) return 0; // if we're at first cell (0, 0) if (m == 0 && n == 0) { if (mat[0][0] - cost == 0) return 1; else return 0; } // if we're at first row, we can only go left if (m == 0) return countPaths(mat, 0, n - 1, cost - mat[m][n]); // if we're at first column, we can only go up if (n == 0) return countPaths(mat, m - 1, 0, cost - mat[m][n]); // recuse to count total paths by going both left and top return countPaths(mat, m - 1, n, cost - mat[m][n]) + countPaths(mat, m, n - 1, cost - mat[m][n]); } // main function int main() { int mat[M][N] = { { 4, 7, 1, 6 }, { 5, 7, 3, 9 }, { 3, 2, 1, 2 }, { 7, 1, 6, 3 } }; int cost = 25; cout << "Total paths with cost " << cost << " are " << countPaths(mat, M-1, N-1, cost); return 0; } |

**Output: **

Total paths with cost 25 are 2

The time complexity of above solution is exponential as we’re doing a lot of redundant work as the same sub-problems are getting computed again and again. As the recursion grows deeper in bigger matrices, 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 total number of paths with cost c to reach 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.

**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 61 62 63 64 65 66 67 68 69 70 |
#include <bits/stdc++.h> using namespace std; // M x N matrix #define M 4 #define N 4 // create a map to store solutions of subproblems unordered_map<string, int> lookup; // Naive recursive top-down function to count total number of paths // to reach cell (m, n) from cell (0, 0) and having given cost int countPaths(int mat[][N], int m, int n, int cost) { // base case if (cost < 0) return 0; // if we're at first cell (0, 0) if (m == 0 && n == 0) { if (mat[0][0] - cost == 0) return 1; else return 0; } // construct a unique map key from dynamic elements of the input string key = to_string(m) + "|" + to_string(n) + "|" + to_string(cost); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // if we're at first row, we can only go left if (m == 0) lookup[key] = countPaths(mat, 0, n - 1, cost - mat[m][n]); // if we're at first column, we can only go up else if (n == 0) lookup[key] = countPaths(mat, m - 1, 0, cost - mat[m][n]); // recuse to count total paths by going both left and top else lookup[key] = countPaths(mat, m - 1, n, cost - mat[m][n]) + countPaths(mat, m, n - 1, cost - mat[m][n]); } // return total number of paths to reach cell (m, n) return lookup[key]; } // main function int main() { int mat[M][N] = { { 4, 7, 1, 6 }, { 5, 7, 3, 9 }, { 3, 2, 1, 2 }, { 7, 1, 6, 3 } }; int cost = 25; cout << "Total paths with cost " << cost << " are " << countPaths(mat, M-1, N-1, cost); return 0; } |

**Output: **

Total paths with cost 25 are 2

The time complexity of above solution is O(M x N x cost).

**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 🙂