A man is located at the top-left corner of a mxn  grid .

he can only move either down or right at any point in time. he has to reach the bottom-right corner of the grid

How many possible unique paths are there?

Example 1:

```Input: m = 3, n = 7
Output: 28
```

Example 2:

```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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
```

Example 3:

```Input: m = 7, n = 3
Output: 28
```

Example 4:

```Input: m = 3, n = 3
Output: 6
```

method 1 :

using recursion

c++ implementation:

``` int rec(int m, int n,int x,int y)
{
if(x>=m || y>=n)
return 0;
else if(x==m-1 && y== n-1)
return 1;
else
{
return rec(m,n,x+1,y)+rec(m,n,x,y+1);
}
}
int uniquePaths(int m, int n) {

return rec(m,n,0,0);

}```

Time Complexity: exponential
space Complexity: exponential

method 2 :

using dynamic programming

c++ implementation:

``` int uniquePaths(int m, int n)
{
int dp[m][n];

for(int i=0;i<m;i++)
dp[i][0]=1;
for(int j=0;j<n;j++)
dp[0][j]=1;

for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}

return dp[m-1][n-1];

}```

Time Complexity: O(mxn)
space Complexity: O(mxn)

method 3 :

using combinations:

C(N,R) =    N! / ((N-R)! R!)

shortform eq: C(10,3)= (10*9*8)/(3*2*1)

c++ implementation:

``` int uniquePaths(int m, int n) {       int N=m+n-2;
int R=m-1;
double c=1;
for(int i=1;i<=R;i++)
{
c=c*(N-R+i)/i;
}
return c;
}```
Time Complexity: O(m-1)
space Complexity: O(1)

also try Unique Paths II

darkmode