題目描述:一個 m×n 的網格,機器人從左上角出發,只能向右或向下移動,求到達右下角的不同路徑數。
解題思路:任意格子 (i, j) 的路徑數 = 來自上方 (i-1, j) 的路徑數 + 來自左方 (i, j-1) 的路徑數。第一行和第一列都只有 1 條路徑。可用數學公式(組合數 C(m+n-2, m-1))直接計算,但 DP 更直觀且避免大數溢位。
時間複雜度:O(m × n) — 填充整個 DP 表格。
空間複雜度:O(m × n),可優化為 O(n)(只保留一行)。
1. Create m×n DP table initialized to 1 2. For i from 1 to m-1, j from 1 to n-1: dp[i][j] = dp[i-1][j] + dp[i][j-1] 3. Return dp[m-1][n-1]
遞迴無記憶 O(2^(m+n)):嘗試向下或向右,重複計算。
數學組合 C(m+n-2, m-1) O(m+n):答案為「從 m×n 網格角落走到終點的路數」即二項式係數 — 代碼簡潔但需防溢位。