Number of Unique Paths
Given a M X N matrix with initial position at top-left cell, find the number of possible unique paths to reach the bottom right cell of the matrix from the initial position. Possible moves can be either down or right at any point in time.
Input:
The first line contains an integer T,
depicting total number of test cases.
Then following T lines contains two integers
m and n depicting the size of the grid.
Output:
Print the number of unique paths to reach
bottom-right cell from the top-left cell.
Example with explanation:
Input:
2
3 3
3 4
Output:
6
10
So, for the first test case, M=3, n=3
Grid is like,

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

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

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

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

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

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

This are the possible unique paths and hence count is 6.
Given a matrix with an initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position. Possible moves can be either or at any point in time.
Recursion Algorithm:
So, the algorithm can be:
But this would generate many overlapping subproblems, which will be computed again and again increasing the time complexity. Hence, we can convert the recursion to dynamic Programming.
Dynamic Programming approach:
C++ Implementation:
Output