[Leetcode] Unique Paths – Dynamic Programming 的應用

題目

Leetcode 62. Unique Paths

給一個 m x n 的棋盤,從左上角的格子出發,規定只能往右走跟往下走,問要到達右下角的格子可以有幾種路徑

Example:

Input: m = 3, n = 3
Output: 6

思路

找出 dp 方程式,例如這題,因為規定只能往右跟往下走,

每一格的結果是由:上面的格子 + 左邊的格子 的結果 (如下圖)

dp 方程式為: dp[i][j] = dp[i-1][j] + dp[i][j-1]

以下列出 3 x 3 所有 6 種路徑

程式碼

▼ Swift 可以用 Array 的 set default value 的 function,做出 2D array,即 array of array

class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        
        if m == 0 || n == 0{
            return 0
        }
        
        var dp = Array(repeating:Array(repeating:1,count:n), count:m)
        for i in 1..<m {
            for j in 1..<n {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]                
            }            
        }        
        return dp.last?.last ?? 0
    }
}

▼ 至於為什麼 default 值要給 1 呢?

因為當 dp[i][0] 跟 dp[0][j] 都是一種路徑,所以預設給 1,而其他格子也給 1 是因為方便偷懶XD 更好的寫法也許是操縱 dp[i][0] 跟 dp[0][j] 給值 1 就好

▼ 填上每一格的路徑數

時間複雜度: O(m x n)

空間複雜度: O(m x n)

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *