runtime 0 ms, beats 100% of cpp submissions
O(min(m,n)) solution with explanation

tags: math

Unique Paths

📖 description

給定兩個數字表示一個 2 維陣列，請求所有從 (0,0) 到 (m,n) 的路徑數量，且只能向下或右走。 

ex.
    Input: 
        m = 3, n = 7
    Output: 
        28

🧠 solution

本題可以使用 dp 的方法，維護一個 2 維陣列，*(i,j)* 內的數值表示從 (0,0) 到 (i,j) 可以走的路徑總數，最後只需要回傳 (m-1,n-1) 的數值即可。
但實際上我們可以利用數學的想法來解題。

    1. Right -> Down -> Down
    2. Down -> Down -> Right
    3. Down -> Right -> Down

    因為只能向下或右走，所以可以採取的動作是固定的，此時可以使用重複組合的概念
    路徑總數為 3!/(2!*1!)

⏳ time complexity

挑選最短的一邊，然後取 nCr 即可，時間複雜度 O(min(m,n))
總時間複雜度 O(min(m,n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {    
public:
    int uniquePaths(int m, int n) {
        int N = m + n - 2;
        int r = min(m,n)-1; // 對最小邊計算
        long sum = 1;

        // nCr
        for(int i = 1; i <= r; i++){
            sum = sum * (N - r + i) / i;
        }
        return (int)sum;
    }
};