## Robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it.

We need to Count All paths from top left to bottom right of a mXn matrix,

**Method1 Recursive and DP :**

We can go backword from (M,N) to (1,1)

As we can take only Up and Left Direction one step , from there we can take either M-1 or N-1

int NumberOfWaysMN(int m, int n) { if (m==1 || n ==1) return 1; else { return NumberOfWaysMN(m-1, n) + NumberOfWaysMN(m, n-1); } }//Function

As We can see here, there are two recursive functions with m-1, n & m, n-1. Which requires O(N) in worst case space complexity, We can reduce Space complexity and Extra calculations due to recursion with Dynamic Programming.

Example of Extra Calculations.

for m=5 and n=5, we’ll call

Example of Extra Calculations.

for m=5 and n=5, we’ll call

Fun(5,5) | Fun(4,5) + Fun(5,4) | | Fun(3,5)+Fun(4,4) Fun(4,4)+Fun(5,3)

So clearly we are calculating recursive function with 4,4 twice.. which we can reduce if we store results for Fun(4,4)

We need to store result for m and n so we need 2D array to store results.

#include <iostream> using namespace std; int numberOfPaths(int m, int n) { // Create a 2D table to store results of subproblems int pathCount[m][n]; for (int i = 0; i < m; i++) pathCount[i][0] = 1; for (int j = 0; j < n; j++) pathCount[0][j] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) pathCount[i][j] = pathCount[i-1][j] + pathCount[i][j-1]; } return count[m-1][n-1]; } int main() { cout << numberOfPaths(5, 5); return 0; }

Time Complexity O(M*N) and Space Complexity O(M*N)

### Variant 2 For N*N :

For an NxN square it takes (2N – 2) steps to move from the upper left corner to bottom right corner.

Of these steps, half must be right and half must be down (N – 1 in each direction).

Knowing this, we can look at it as a string permutation or how many ways can you write “RRRDDD”, etc.

(this would be for N = 4, “RRDD” for N = 3 and so on).

Now we just have to count the number of permutations for this string which in terms of N will be (2N – 2)!/((N – 1)!(N – 1)!).

These numbers match up….

2, 2

3, 6

4, 20

5, 70

6, 252

7, 924

8, 3432

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE