Unique Paths 1

 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) 

detailed video explanation for this post(youtube channel :take U forward)

also try Unique Paths II