Unique Paths

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.

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

Constraints:

• 1 <= m, n <= 100

Approach - DP

• check this once
• Time & Space Complexity
  Time complexity: O(m∗n)
  Space complexity: O(n)

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp,1);
 
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[j] += dp[j+1];
            }
        }
 
        return dp[0];
    }
}

Approach - Recursion

• The idea is the end goal would be 1 then we keep adding to right and bottom ad we are using dfs and anything out of bounds would be 0
• Time & Space Complexity
  Time complexity: O(2^(m+n))
  Space complexity: O(m+n)

class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(0,0,m,n);
    }
 
    int dfs(int i, int j, int m, int n) {
        if ((i == m - 1) && (j == n - 1))
            return 1;
 
        if (i >= m || j >= n)
            return 0;
 
        return dfs(i+1,j,m,n) + dfs(i,j+1,m,n);
    }
}