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

此題要我們計算從左上角走到右下角，所有可能的路徑總數。我們可以觀察出來，要從左上角走到右下角，機器人只能向右或向下走。如果機器人向上或向右走的話，那就是往回走了。這樣會有重複路徑的問題。

因為機器人只能向右或向下走，所以當機器人在 A 時，它一定是從 X 或 Y 走過來的。

因此，要到達 A 的路徑總數等於到達 X 的路徑總數加上到達 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;
    }
}

參考

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