## Problem Statement

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?

**Constraints:**

`1 <= m, n <= 100`

- It’s guaranteed that the answer will be less than or equal to
`2 * 10 ^ 9`

.

## Sample Test Cases

Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right

## Problem Solution

We can approach this problem using Dynamic Programming. So, every DP problem has some sub-problem whose solutions leads to our final answer.

Let’s first find the sub-problem.

In this problem our aim is to reach (m,n) we can reach this cell via two paths ie (m-1 , n) and (m, n-1). So, if we have the total no of unique ways to reach (m-1 , n) and (m, n-1) we can easily find the no of unique paths for(m, n) by using the relation-

**F(m, n) = F(m-1, n) + F(m, n-1)**

Subsequently we can extend this relation for F(m, n-1 ) and F(m, n-1) and so on.

But we need to keep in mind that whenever m=0 or n=0 we have to return 1 because when we are in the first row we have only one single unique movement and same is the case when we are in the first column.

## Complexity Analysis

Time Complexity : Since we are traversing the entire dp matrix our time complexity will be O(mn).

Space Complexity : Since we are maintaining the entire dp matrix our space complexity will be O(mn).

## Code Implementation

#include<bits/stdc++.h> using namespace std; int dp[1000][1000]; int uniquePaths(int m,int n) { dp[m][n]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(i==0||j==0) { dp[i][j]=1; } else { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } return dp[m-1][n-1]; } int main() { int m=3; int n=2; int x= uniquePaths(m,n); cout<<x; }