62. Unique Paths | Swift | Aug LeetCoding Challenge 2022

題目

2022/8/1 ，Aug LeetCoding Challenge 2022 的題目

• 題目： https://leetcode.com/problems/unique-paths/
• 難度： Medium

思路

可以拆解成子問題

0 1
1 2

可以發現除了第一排和第一列，每一個元素都是由其上和其左相加而成。因此可以利用 DP 來處理。

資料結構與演算法

• DP
• Memoization table - 減少走訪的次數

程式碼

class Solution {
    var map = [String: Int]()
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        // ① Base Case
        if m == 1 || n == 1 { return 1 }
        
        // ② Memoization
        let mn = "\(m),\(n)"
        let nm = "\(n),\(m)"
        if let value = map[mn] ?? map[nm] { return value }
        
        // ③ Routine
        // 從子 problem 取得結果，計算完先儲存到 memoization table 再回傳
        let value = uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
        map[mn] = value
        map[nm] = value
        
        return value
    }
}

分析

• M - m.count
• N - n.count

時間複雜度

O(M*N)

雖然 memoization table 可以達到 /2 的效果，但是表記上還是會被省略。
如果有理解錯誤請告知！

空間複雜度

O(M*N)