LeetCode Note Java 00062：Unique Paths

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 651 所需閱讀時間 ≈ 2 分鐘

情境題：給定 m * n 的網格，只能往右或往下走，求從左上到右下的所有路徑數。

題目

Unique Paths Medium

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.

我的解法

題目提到了網格，很容易讓人聯想到使用動態規劃來解題。
二維動態規劃，畫表格填充數量來觀察出公式：

n\m 1 2 3 4 5
1 1 1 1 1 1
2 1 2 3 4 5
3 1 3 6 ? ?
4 1 4 ? ? ?
5 1 5 ? ? ?

若是用手來數，數到 3 x 3 就滿極限了，後面就不容易數出正確答案。
以僅有數值來分析，每個數值表示的是到達該格的方法數。
由於只能往右方或下方移動，所以可以確定上一格一定是來自左方或上方。
因此可以得知，到達某一格的方法數 為 到達上方格的方法數 加上 到達左方格的方法數。
還有可以發現當某邊為 1 時，都只會有一種到達方法，將此規則套入公式就能讓程式有初始值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] table = new int[m][n];
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
              table[i][j] = 1;
            } else {
              table[i][j] = table[i - 1][j] + table[i][j - 1];
            }
          }
        }
        return table[m - 1][n - 1];
    }
}

檢討

看了別人答案，發現這題效能要好就必須將此問題視為排序問題，將固定次數的 下 跟 右 進行排列組合。
(不過我排列組合老早就忘光了😥，所以不可能想出這解法)

題目中 m 跟 n 為格子數，要轉成步數就要減 1，變成 m - 1 跟 n - 1。
排序的公式為：總數量階除以各重複數量階 => (a + b)! / (a! * b!) => ((m - 1) + (n - 1))! / ((m - 1)! * (n - 1)!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        m--;
        n--;
        if(m < n) {              // Swap, so that m is the bigger number
            m = m + n;
            n = m - n;
            m = m - n;
        }
        long res = 1;
        int j = 1;
        for(int i = m+1; i <= m+n; i++, j++){       // Instead of taking factorial, keep on multiply & divide
            res *= i;
            res /= j;
        }
            
        return (int)res;
    }
}

結論是我看過這用法之後，在實戰中應該還是用不出來…

參考資料

Math solution, O(1) space