LeetCode Unique Paths：動態規劃求網格路徑數

題目大意

m × n 網格，機器人從左上角 (0,0) 走到右下角 (m-1,n-1)，每步只能向右或向下。求不同路徑總數。

動態規劃解法

定義 `dp[i][j]` = 從起點走到 (i,j) 的路徑數。

• 狀態轉移：`dp[i][j] = dp[i-1][j] + dp[i][j-1]` （從上方或左方到達）
• 邊界：第一行第一列全為 1（只能一直向右/向下）
• 答案：`dp[m-1][n-1]`

代碼實現

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector> dp(m, vector(n, 1));
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        return dp[m-1][n-1];
    }
};

空間優化：一維 DP

int uniquePaths(int m, int n) {
    vector dp(n, 1); // dp[j] 表示當前行第 j 列
    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j)
            dp[j] += dp[j-1]; // dp[j] 是上一行同列(舊值), dp[j-1] 是當前行左列(新值)
    return dp[n-1];
}

數學組合解法 O(min(m,n))

總步數 = m+n-2，其中向下 m-1 步，向右 n-1 步。
路徑數 = C(m+n-2, m-1) = C(m+n-2, n-1)

int uniquePaths(int m, int n) {
    long long ans = 1;
    for (int i = 1; i <= min(m,n)-1; ++i) {
        ans = ans * (max(m,n)-1 + i) / i; // 逐步乘除防溢出
    }
    return (int)ans;
}

複雜度對比

延伸：Unique Paths II（含障礙）

若網格有障礙物 (1 表示障礙)，`dp[i][j] = 0` 若該格為障礙，否則同樣轉移。初始化時遇障礙後續全為 0。