62. Unique Paths

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

62Unique Paths2-D DPMedium2-D DP

給定一個 m x n 的網格，機器人從左上角出發，每次只能往右或往下移動一步。求到達右下角共有多少條不同路徑。

Example:

Input: m = 3, n = 7 Output: 28

Intuition

TIP

每個格子的路徑數等於「上方格子」加「左方格子」的路徑數。

機器人只能往右或往下，所以到達 (i, j) 的方式只有從 (i-1, j) 或 (i, j-1) 過來
第一行和第一列的路徑數都是 1（只有一種走法）
這是最經典的網格型 2D DP 問題

Approaches

1. 2D DP Table — O(m * n) / O(m * n)

Idea: 建立 m x n 的 DP 表格，dp[i][j] 代表到達 (i, j) 的路徑數，轉移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]
Time: O(m * n)
Space: O(m * n)

class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        val dp = Array(m) { IntArray(n) { 1 } }
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }
}

⭐ 2. 1D DP (Space Optimized) — O(m * n) / O(n)

Idea: 由於每一行只依賴上一行，可以用一維陣列滾動更新。dp[j] += dp[j-1]，其中 dp[j] 保留的是上一行的值（即「上方」），dp[j-1] 是當前行已更新的值（即「左方」）。
Time: O(m * n)
Space: O(n)

class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        val dp = IntArray(n) { 1 }
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[j] += dp[j - 1]
            }
        }
        return dp[n - 1]
    }
}

Note: Combinatorics Approach

Idea: 從左上到右下總共要走 (m-1) + (n-1) 步，其中選 m-1 步往下（或 n-1 步往右），答案就是 C(m+n-2, m-1)。
Time: O(min(m, n))
Space: O(1)

class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        val total = m + n - 2
        val k = minOf(m - 1, n - 1)
        var result = 1L
        for (i in 1..k) {
            result = result * (total - k + i) / i
        }
        return result.toInt()
    }
}

🔑 Takeaways

Pattern: 網格型 DP — dp[i][j] = dp[i-1][j] + dp[i][j-1]
Key trick: 2D DP 表格若只依賴上一行，可壓縮為 1D 陣列；排列組合有時能直接算出答案

Intuition

Approaches

🔑 Takeaways

相關題目