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

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

                   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;
}