Given a `M x N` rectangular grid, efficiently count all paths starting from the first cell `(0,0)` to the last cell `(N-1,M-1)` in the grid. We can either move down, or move towards right from a cell.

For example,

**Input: ** 3 x 3 matrix

**Output: ** Total number of paths are 6

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)

(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)

(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2)

(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2)

(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)

(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2)

The idea is to start from the top-left corner of the matrix and recurse for the next cell which can be either immediate right cell or immediate bottom cell. We can easily maintain the path count as we move along in the recursion as shown below.

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 |
#include <stdio.h> // M x N matrix #define M 3 #define N 3 // Top-down recursive function to count all paths from the cell (m,n) // to the last cell (N-1,M-1) in a given M x N rectangular grid int countPaths(int m, int n) { // there is only one way to reach the last cell // when we're at the last row or the last column if (m == M - 1 || n == N - 1) return 1; return countPaths(m + 1, n) // move down + countPaths(m, n + 1); // move right } // main function int main(void) { int k = countPaths(0, 0); printf("Total number of paths are: %d", k); return 0; } |

`Output:`

Total number of paths are: 6

The time complexity of above solution is exponential since the problem exhibits overlapping subproblems i.e. it computes solutions to the same sub-problems again and again. The problem also has an optimal substructure as solution to the problem can be derived using solution to its sub-problems. Now since both properties of dynamic programming are satisfied, it can be used to optimize the code.

We can either store results of the function calls and return those results when the same input occurs again or construct an auxiliary matrix to store results of the smaller sub-problems. Below code follows the later approach:

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 |
#include <stdio.h> // M x N matrix #define M 3 #define N 3 // Bottom-up function to count all paths from the first cell (0,0) // to the last cell (M-1,N-1) in a given M x N rectangular grid int countPaths(int m, int n) { // T[i][j] stores the number of paths from cell (0,0) to cell (i,j) int T[m][n]; // There is only one way to reach any cell in the first column // i.e. to move down for (int i = 0; i < m; i++) T[i][0] = 1; // There is only one way to reach any cell in the first row // i.e. to move right for (int j = 0; j < n; j++) T[0][j] = 1; // fill T[][] in bottom-up manner for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { T[i][j] = T[i-1][j] + T[i][j-1]; } } // last cell of T[][] stores the count of paths from cell(0,0) to cell(i,j) return T[m-1][n-1]; } // main function int main(void) { int k = countPaths(M, N); printf("Total number of paths are: %d", k); return 0; } |

`Output:`

Total number of paths are: 6

The time complexity of the above solution is `O(M x N)` and the auxiliary space required by the program is `O(M x N)`. The space complexity of the solution can be improved up to O(N) as we’re only reading data of previous row for filling the current row. Below is the space optimized solution using only single array.

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 |
#include <stdio.h> // M x N matrix #define M 3 #define N 3 // Bottom-up space efficient function to count all paths from the first // cell (0,0) to the last cell (M-1,N-1) in a given M x N rectangular grid int countPaths(int m, int n) { int T[n]; T[0] = 1; // fill T[][] in bottom-up manner for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { T[j] += T[j - 1]; } } // return last cell return T[n-1]; } // main function int main(void) { int k = countPaths(M, N); printf("Total number of paths are: %d", k); return 0; } |

`Output:`

Total number of paths are: 6

We can also find the number of paths from the first cell `(0,0)` to the last cell `(m-1,n-1)` using a direct formula. To reach the last cell, we have to take `(m-1)` steps to the right and `(n-1)` steps down. So the total steps are `(m-1)+(n-1) = m+n-2`. Out of these `(m+n-2)` steps, any `(n-1)` steps can be down and any `(m-1)` steps can be towards right. So, the total number of ways are ` ^{(m+n-2)}C_{(n-1)}` or

`.`

^{(m+n-2)}C_{(m-1)}

**Suggested Post:** How to print all paths from first cell to last cell

**Exercise:** Extend the solution for diagonal moves (down-right).

**Thanks for reading.**

Please use our online compiler to post code in comments.

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

## Leave a Reply