LeetCode Unique Paths 解題詳解：組合數學與動態規劃雙解法

問題描述

m×n 網格，從左上角走到右下角，只能向下/向右，求不同路徑總數。m,n ≤ 100。

解法一：動態規劃（一維滾動數組）

dp[j] 為到達當前行第 j 列路徑數。初始 dp[0]=1。每行更新：dp[j] += dp[j-1]（j 從 1 開始）。

int uniquePaths(int m, int n) {
    vector dp(n, 0);
    dp[0] = 1;
    for (int i=0;i

解法二：組合數學公式
總共需走 m-1 步向下、n-1 步向右，共 m+n-2 步。選擇其中 m-1 步作為向下（或 n-1 步向右），路徑數 = C(m+n-2, m-1)。
long long uniquePathsMath(int m, int n) {
    long long ans = 1;
    int N = m + n - 2, K = min(m-1, n-1);
    for (int i=1; i<=K; ++i) {
        ans = ans * (N - K + i) / i; // 分子分母同步約分，防溢出
    }
    return ans;
}

複雜度對比

方法
時間
空間
備註
DP
O(mn)
O(n)
通用，易擴展到障礙物
組合數學
O(min(m,n))
O(1)
最快，需防溢出（用 long long 除法同步約分）


推薦
面試首選組合數學解法展示數學功底，工程實踐中 DP 更易維護擴展。