LeetCode 不同路徑：組合數學與動態規劃雙解法

題目描述

機器人從 m x n 網格左上角走到右下角，只能向右/向下移動，求不同路徑總數。

範例：

m = 3, n = 7 → 28
圖示: 3行7列網格，共需走 2+6=8 步，其中 2 步向下，6 步向右

解法一：組合數學公式 O(min(m,n))

總步數 m+n-2，其中 m-1 步向下，n-1 步向右。路徑數 = 選擇向下步驟位置的組合數：

C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)

為避免溢出，迭代計算：result = result * (n+i) / i（i=1..m-1）。

解法二：動態規劃 O(mn) 時間 O(n) 空間

dp[j] 表示到達當前行第 j 列的路徑數。遞推：dp[j] += dp[j-1]。首行首列初始化為 1。

Python 參考實現

import math

class Solution:
    # 組合數學解法
    def uniquePathsMath(self, m, n):
        m, n = m - 1, n - 1
        return math.factorial(m + n) // (math.factorial(m) * math.factorial(n))
    
    # DP 解法（一維優化）
    def uniquePaths(self, m, n):
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[-1]

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.uniquePaths(3, 7) == 28
    assert sol.uniquePathsMath(3, 7) == 28
    assert sol.uniquePaths(1, 1) == 1
    print("所有測試通過")

核心要點總結

• 數學本質：路徑即「在總步驟中選擇向下位置」的組合問題
• DP 直觀：dp[i][j] = dp[i-1][j] + dp[i][j-1]，一維優化後極簡潔
• 複雜度權衡：數學解 O(min(m,n)) 最優，DP 解 O(mn) 更易擴展（如加障礙、權重）
• 變體基石：LeetCode 62/63/64/174 均建立在此模型上

不同路徑是網格問題的「Hello World」，雙解法對比深化對「組合計數」與「動態規劃」兩種思維模式的理解。