62. Unique Paths

解題思路

直覺想到高中數學的排列組合。套公式為 C(m+n-2, m-1)，也就是 (m+n-2)! / (m-1)!(n-1)!。

寫成程式的話，必須進一步化簡計算量，模擬分母 (m+n-2)! 跟 (m-1)!, (n-1)! 中較大的數字約分，以及乘上(m-1)!, (n-1)! 中較小的數字。

可以進一步一邊乘 (top-i) 又一邊除 (i+1) 而不會說數字無法整除而有錯，背後的想法是連續整數在同樣乘或除第N個數的時候，因為連續的特性所以就能除盡。

也可以用 DP，下次試看看。

程式碼

class Solution {
public:
    int uniquePaths(int m, int n) {
        int top = m + n - 2;
        int down = min(m, n) - 1;

        long long int ans = 1;
        for(int i=0; i<down; i++)
        {
            ans = ans * (top - i) / (i + 1);
        }
        return ans;
    }
};