Skip to content

Unique Paths⚓︎

Link

Description⚓︎

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 * 10^9.

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:

  • Right -> Down -> Down

  • Down -> Down -> Right
  • Down -> Right -> Down

Constraints:

  • 1 <= m, n <= 100

Solution⚓︎

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int dp[110][110];
    int uniquePaths(int m, int n) {
        for (int i = 0; i < 110; i++) dp[i][0] = dp[0][i] = 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(m\times n)\);
  • Space complexity: \(O(m\times n)\).

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int dp[110];
    int uniquePaths(int m, int n) {
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int j = 1; j < m; j++)
            for (int i = 1; i < n; i++)
                dp[i] += dp[i - 1];
        return dp[n - 1];
    }
};
  • Time complexity: \(O(m\times n)\);
  • Space complexity: \(O(n)\).