62. Unique Paths

Problem

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

Solution

This problem asks us to calculate the total number of all possible paths from the top-left corner to the bottom-right corner. We can observe that to go from the top-left corner to the bottom-right corner, the robot can only go right or down. If the robot goes up or right, it is going back. This will cause the problem of duplicate paths.

Since the robot can only go right or down, when the robot is at A, it must have come from X or Y.

Therefore, the total number of paths to A is equal to the total number of paths to X plus the total number of paths to Y.

Dynamic Programming

• Time:
• Space:

class Solution {
    public int uniquePaths(int m, int n) {
        return uniquePaths(m - 1, n - 1, new int[m][n]);
    }

    private int uniquePaths(int m, int n, int[][] dp) {
        if (m == 0 && n == 0) return 1;
        if (dp[m][n] != 0) return dp[m][n];

        int paths = 0;
        if (m > 0) {
            paths += uniquePaths(m - 1, n, dp);
        }
        if (n > 0) {
            paths += uniquePaths(m, n - 1, dp);
        }

        dp[m][n] = paths;
        return paths;
    }
}

Reference

• 62. Unique Paths, LeetCode.
• 62. Unique Paths, LeetCode Solutions.