There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

&nbsp;
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 -&gt; Down -&gt; Down
2. Down -&gt; Down -&gt; Right
3. Down -&gt; Right -&gt; Down


&nbsp;
Constraints:


	1 &lt;= m, n &lt;= 100


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dfs(i ,j):
            if i == 0 and j == 0: return 1
            elif i < 0 or j < 0: return 0
            
            return dfs(i-1, j) + dfs(i, j-1)
        return dfs(m-1, n-1)
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        
        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                dp[i][j] = -1;
            }
        }
        
        return helper(m, 0, n, 0, dp);
    }
    
    private int helper(int m, int i, int n, int j, int[][] dp) {
        if(i == m || j == n) {
            return 0;
        }
        
        if(i == m-1 && j == n-1) {
            dp[i][j] = 1;
        }
        
        if(dp[i][j] == -1) {
            dp[i][j] = helper(m, i+1, n, j, dp) + helper(m, i, n, j+1, dp);
        }
        
        return dp[i][j];
    }
}
#define vi vector<int>
#define vvi vector<vi>
class Solution {
public:
    
    int countPath(vvi& dp,int r,int c, int m , int n){
          if(m==r-1 || n==c-1)
              return 1;
           
        if(dp[m][n]!=-1)
            return dp[m][n];
        
       return dp[m][n] = countPath(dp,r,c,m+1,n) + countPath(dp,r,c,m,n+1);
    }
    int uniquePaths(int m, int n) {
        
        vvi dp(m,vi(n,-1));
        
        return countPath(dp,m,n,0,0);
    }
};
var uniquePaths = function(m, n) {
    let count = Array(m)
    for(let i=0; i<m; i++) count[i] = Array(n)
    for(let i=0; i<m; i++){
        for(let j=0; j<n; j++){
            if(i == 0 || j == 0) count[i][j] = 1
            else count[i][j] = count[i][j-1] + count[i-1][j]
        }
    }
    return count[m-1][n-1]
};
Unique Paths