這邊給大家介紹一道有關高中數學的排列組合問題
參考題目: 62. Unique Paths

題意: 給定m*n個方格，機器人站在左上角要走到右下角，只能往右邊或下邊走，
全部有幾種走法?

譬如說:

Input: m = 3, n = 2
Output: 3
說明:
三種走法為
1. 右右下
2. 右下右
3. 下右右

其實這一題如果數學好的話就很簡單，
有m*n個方格，要走到右下角需要
往右走m-1步，
往下走n-1步，
相當於是m-1個「右」和n-1個「下」的文字排列，
方法數為C(m+n-2,m-1)(或C(m+n-2,n-1))

至於要如何計算組合數C(n,k)呢?
有兩種方法:
一種是用可以支援大數運算的語言，如python，
用乘法的公式C(n,k)=(n!)/[(n-k)!(k!)]硬算，不怕溢位

若用c++的話則可以用動態規劃的方法避免溢位(可參考leetcode- 119. Pascal's Triangle II)

c++解法

class Solution {
public:
    long long Cnk(int n, int k) {
        vector<long long> pas(k+1, 1);
        for(int i=1; i<n; i++){
            for(int j=min(i,k); j>0;j--){
                pas[j]+=pas[j-1];
            }
        }
        return pas[k];
    }
    int uniquePaths(int m, int n) {
        return Cnk(m+n-2,min(m-1, n-1));
    }
};

python 解法

class Solution:
    def Cnk(self, n, k):
        ans = 1
        for i in range(k):
            ans *= n-i
        for i in range(k):
            ans //= i+1
        return ans
    def uniquePaths(self, m: int, n: int) -> int:
         return self.Cnk(m+n-2,m-1)

或者可以寫得更簡潔:

class Solution:
    def Cnk(self, n, k):
        return factorial(n)//factorial(n-k)//factorial(k)
    def uniquePaths(self, m: int, n: int) -> int:
         return self.Cnk(m+n-2,m-1)