62. Unique Paths

Medium

Description

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

Example:

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

Intuition#

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

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

Approaches#

1: 2D DP Table#

概念: 建立 m x n 的 DP 表格，dp[i][j] 代表到達 (i, j) 的路徑數，轉移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]
時間複雜度: O(m * n)
空間複雜度: 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（空間優化）#

概念: 由於每一行只依賴上一行，可以用一維陣列滾動更新。dp[j] += dp[j-1]，其中 dp[j] 保留的是上一行的值（即「上方」），dp[j-1] 是當前行已更新的值（即「左方」）。
時間複雜度: O(m * n)
空間複雜度: 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]
    }
}

補充：組合數學解法

概念: 從左上到右下總共要走 (m-1) + (n-1) 步，其中選 m-1 步往下（或 n-1 步往右），答案就是 C(m+n-2, m-1)。
時間複雜度: O(min(m, n))
空間複雜度: 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]
關鍵技巧: 2D DP 表格若只依賴上一行，可壓縮為 1D 陣列；排列組合有時能直接算出答案