Unique Paths
題目描述
一個 m × n 的網格，機器人在左上角 (0,0)，目標在右下角 (m-1, n-1)。每次只能往下或往右走。回傳不同路徑的數量。
輸入：m = 3, n = 7
輸出：28
輸入：m = 3, n = 2
輸出：3
解題思路
定義狀態
dp[i][j] = 從 (0,0) 到 (i,j) 的不同路徑數
邊界條件
第一行 dp[0][j]=1（只能一路向右），第一列 dp[i][0]=1（只能一路向下）
轉移方程
dp[i][j] = dp[i-1][j] + dp[i][j-1]。到達 (i,j) 只能從上方 (i-1,j) 或左方 (i,j-1) 過來
空間優化
逐行計算時，dp[j] 更新前存著上一行的值（即 dp[i-1][j]），dp[j-1] 已更新為當前行的值（即 dp[i][j-1]）
回傳結果
dp[n-1]（一維優化後）或 dp[m-1][n-1] 即為答案
程式碼
C#
public class Solution {
public int UniquePaths(int m, int n) {
// 空間優化：用一維陣列
int[] dp = new int[n];
Array.Fill(dp, 1); // 第一行全是 1
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];
}
}TypeScript
function uniquePaths(m: number, n: number): number {
const dp = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}Python
def uniquePaths(m: int, n: int) -> int:
dp = [1] * n # 第一行都是 1
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1] # 上方 + 左方
return dp[n - 1]複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(m × n) | O(n) |
- Time：填一個 m×n 的表格，每格常數操作
- Space：空間優化後只保留一行（長度 n），逐行覆蓋更新
圖解
3×3 的 DP 表格：邊界（第一行和第一列）都是 1，內部格子等於上方加左方。 例如 (1,1)=2 來自上方 (0,1)=1 加左方 (1,0)=1；最終 (2,2)=6 是答案。
進階觀點
💡面試追問
Q: 數學解法怎麼做？ A: 從左上到右下共走 (m-1)+(n-1) = m+n-2 步，其中選 m-1 步向下（其餘向右），答案是組合數 C(m+n-2, m-1)。計算時要注意大數溢位，可以用逐步除法或取模處理。
Q: Unique Paths II（有障礙物）怎麼改？ A: 在 DP 初始化和轉移時，遇到障礙格子直接設 dp=0（不可到達），其餘邏輯不變。如果起點或終點是障礙則直接回傳 0。第一行/列若中途有障礙，障礙之後的格子也都是 0。
Q: Minimum Path Sum（帶權版）的差異？
A: 轉移從加法改成取 min：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])，框架完全相同，只是聚合函數從「求和」變成「取最小」。
Q: 空間優化的關鍵洞察是什麼？
A: 逐行計算時 dp[j] 在被更新前是上一行的值（dp[i-1][j]），而 dp[j-1] 已被更新為當前行的值（dp[i][j-1]），所以 dp[j] += dp[j-1] 完美等價 2D 轉移，不需要兩個陣列。
邊界情況
- m 或 n 等於 1：只有一行或一列，只有一條路徑，答案為 1
- m 和 n 都很大（如 100×100）：dp 值會很大但不超過 C(198,99)，在 64 位整數範圍內
- m 等於 n：結果具有對稱性，C(2n-2, n-1)，等同 Catalan 數的相關公式
理解測驗
🤔 為什麼第一行和第一列的路徑數都是 1？
🤔 空間優化中 dp[j] += dp[j-1] 為什麼等價於 dp[i][j] = dp[i-1][j] + dp[i][j-1]？