Robot in an MXN grid

Problem: A robot is located at the top-left corner of a m x n grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid .
How many possible unique paths are there?

Approach 1(Recursion):

Let NumberOfPaths(m, n) be the count of paths to reach row number m and column number n in the matrix, NumberOfPaths(m, n) can be recursively written as following.

```/ Returns count of possible paths to reach cell at row number m and column
// number n from the topmost leftmost cell (cell at 1, 1)
int  numberOfPaths(int m, int n)
{
// If either given row number is first or given column number is first
if (m == 1 || n == 1)
return 1;

// If diagonal movements are allowed then the last addition
// is required.
return  numberOfPaths(m-1, n) + numberOfPaths(m, n-1);
// + numberOfPaths(m-1,n-1);
}
```

The time complexity of above recursive solution is exponential.

Approach 2(Dynamic Programming):

This problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array count[][] in bottom up manner using the above recursive formula.

```int numberOfPaths(int m, int n)
{
// Create a 2D table to store results of subproblems
int count[m][n];

// Count of paths to reach any cell in first column is 1
for (int i = 0; i < m; i++)
count[i][0] = 1;

// Count of paths to reach any cell in first column is 1
for (int j = 0; j < n; j++)
count[0][j] = 1;
<strong>
// Calculate count of paths for other cells in bottom-up manner using
// the recursive solution
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)

// By uncommenting the last part of the code calculates the total
// possible paths if the diagonal Movements are allowed
count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1];

}
return count[m-1][n-1];
}
```

Time complexity of the above dynamic programming solution is O(mn).

Note: Count can also be calculated using the formula (m-1 + n-1)!/(m-1)!(n-1)!.
See this for explanation of above formulae.