LeetCode 62. Unique Paths 唯一路徑

題目: 一個機器人位於 m x n 網格的右上角. 機器人只能向右或者向下. 機器人試圖到達右下角. 問有多少種不重覆的路徑?
上圖是一個 3 x 7 的網格. m 和 n 最大為 100.
鏈接: https://leetcode.com/problems/unique-paths/

方法一: 自上而下的遞歸

如圖, 到達 Finish 點 (3, 7) 的所有不重覆路徑個數等於到達點 (3, 6) 的路徑個數加上到達點 (2, 7) 的路徑個數. 同理: (3, 6) = (3, 5) + (2, 6) .....
當 m = 1 或 n = 1 時, 只有一條路徑. 這是遞歸的終止條件.
具體的代碼如下:

    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        else
            return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    } 

LeetCode 上提交後顯示超時了, 預料之中.... 一般有返回值的遞歸都比較耗時, 因為要保存所有的未計算的節點.

方法二: 自下而上的迴圈

自上而下的遞歸不行, 我們可以嘗試自下而上的迴圈, 把每一次的計算結果保存在二維數組中.例如 matrix[1][2] = 3 代表從 (1, 1) 到達 (2, 3) 共有 3 種不同的路徑(數組下標從 0 開始, 所以 (m, n) 對應 matrix[m-1][n-1]). 從 matrix[0][0] 一直計算到 matrix[99][99], 因為 LeetCode 測試用例有幾十個, 所以將計算結果保存到靜態成員變數中, 只計算一次就可以了.

    static int[][] matrix = new int[100][100];
    static {
        matrix[0][0] = 1;
        for (int i = 1; i < 100; i++) {
            matrix[i][0] = 1;
            matrix[0][i] = 1;
        }
        for (int m = 1; m < 100; m++) {
            for (int n = 1; n < 100; n++) {
                matrix[m][n] = matrix[m][n - 1] + matrix[m - 1][n];
            }
        }
    }
    // 自下而上把算出來的值存入二維數組中(100X100),然後直接取用
    public int uniquePaths2(int m, int n) {
        return matrix[m - 1][n - 1];
    }  

提交後顯示用時 9ms,仍然不夠快.

方法三

把我們得到的二維數組列印出來, 看看有什麼規律沒有:

斜著看這不就是楊輝三角嗎! 坑啊...

其中, 計算方法為:

(m, n) 對應於上圖的第 (m+n-2) 行, 第 (n-1) 列

    public int uniquePaths3(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        if (m == 2 || n == 2)
            return m >= n ? m : n;
        if (m >= n)
            return (int) (f( m + n - 2, m) / f( n - 1, 1));
        else
            return (int) (f( m + n - 2, n) / f( m - 1, 1));
    }
 
    //階乘.不能用 int, 因為 13 的階乘就超過 int 的範圍了
    public static long f(int a, int b) {
    long result = (long) a;
    for (int i = a - 1; i > b - 1; i--)
        result *=  i;
    return result;
    }

提交後顯示用時 0 ms, 夠快了.