 # Find total number of unique paths in a grid

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

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

Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.