終於來到最後一篇介紹 LeetCode 演算法的導讀文了，先聲明其實還有一些主題沒有介紹，在安排三十天挑戰計畫裡面，因為整個主題不是全部 LeetCode，是環繞在製作 App 時需要的觀念，在篇幅上有些修剪，所以挑出重點觀念說明，而 SwiftUI 也是這樣的取捨，因為本系列終極目標是製作 LeetCode 的觀念 App。

回歸正題，最後一個主題是 Dynamic Programming，中文是「動態規劃」，這類的解法是以空間換取時間，通常是二維陣列，更省空間會用到一維陣列。

費式數列介紹

最常被介紹的就是費式數列，公式為：

f(n)=f(n−1)+f(n−2)

它的數值關係如下，這題是 LeetCode 509. Fibonacci Number 題。

• f(1) = 1
• f(2) = 2
• f(3) = f(3-1) + f(3-2) = f(2) + f(1) = 3
• f(4) = f(4-1) +f(4-2) = f(3) + f(2) = 3 + 2 = 5
• f(5) = f(5-1) +f(5-2) = f(4) + f(3) = 5 + 3 = 8

而在寫程式的時候會很直接的照著公式寫邏輯，但是這樣就會遞迴很多次造成時間複雜度快速增加。

class Solution {
    func fib(_ n: Int) -> Int {
        if n == 0 { return 0 }
        if n == 1 { return 1 }
        return fib(n-1) + fib(n-2)
    }
}

• 時間複雜度：O(2^n)
• 空間複雜度：O(n) （遞迴調用的深度）

利用動態規劃 (DP) 優化後，程式碼如下，使用陣列去紀錄上一次計算結果，我們就不用再次計算上次的數值，就是前面提到的用空間換取時間的概念。

class Solution {
    func fib(_ n: Int) -> Int {
        if n == 0 { return 0 }
        if n == 1 { return 1 }
        
        var dp = Array(repeating: 0, count: n + 1)
        dp[0] = 0
        dp[1] = 1
        
        for i in 2...n {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        
        return dp[n]
    }
}

• 時間複雜度：O(n)
• 空間複雜度：O(n)

還有其他經典題目，這邊列幾個主題給讀者去深入研究。

1. 最長上升子序列（Longest Increasing Subsequence）

2. 背包問題（Knapsack Problem）

3. 最長公共子序列（Longest Common Subsequence）

4. 硬幣找零（Coin Change）

5. 矩陣鏈乘積（Matrix Chain Multiplication）

6. 最長回文子序列（Longest Palindromic Subsequence）

7. 圖的最短路徑問題（Shortest Path）

因篇幅關係無法全介紹，這邊再介紹一題最長上升子序列（Longest Increasing Subsequence），這屬於 LeetCode 300. Longest Increasing Subsequence，難度有到 Medium。

題目給定一個數字陣列，需要返回嚴格遞增數列的最大長度，看起來很抽象，看一下範例就會知道題目要做什麼。

輸入陣列: nums = [10,9,2,5,3,7,101,18]
輸出陣列: 4
說明: 最長的遞增集合是 [2,3,7,101], 因此長度是 4.

為了求出長度，會先建立一個跟 nums 一樣長度的空間陣列去計算。

[1,1,1,1,1,1,1,1]

會有兩個指針去算最長集合，i 索引負責走訪 1 到 nums 長度減一， j 負責走訪 0 到 i。

[10,9,2,5,3,7,101,18]
    ^
  ^
此時 dp[1] = 1

[10,9,2,5,3,7,101,18]
      ^
  - ^
9 < 10
dp[2] = 1

[10,9,2,5,3,7,101,18]
        ^
  - - ^
2 < 9, 2 < 5
dp[3] = dp[2] + 1 = 2

[10,9,2,5,3,7,101,18]
          ^
  - - - ^
2 < 5 > 3
dp[4] = dp[3] = 2

[10,9,2,5,3,7,101,18]
            ^
  - - - - ^
2 < 3
5 > 3 < 7
dp[5] = dp[4] + 1 = 3

[10,9,2,5,3,7,101,18]
               ^
  - - - - - ^
2 < 3 < 7 < 101

dp[6] = dp[5] + 1 = 4

[10,9,2,5,3,7,101,18]
                   ^
  - - - - - -  ^
2 < 3 < 7 < 101 > 18

dp[7] = dp[6] = 4

一步一步走訪以及比較，所以寫成 Swift 程式碼會呈現如下模樣。

func lengthOfLIS(_ nums: [Int]) -> Int {
    if nums.isEmpty { return 0 }
    var dp = Array(repeating: 1, count: nums.count)
    var maxLen = 1
    
    for i in 1..<nums.count {
        for j in 0..<i {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j] + 1)
                maxLen = max(maxLen, dp[i])
            }
        }
    }
    
    return maxLen
}

總結

DP 問題主要還是要先定義清楚索引代表的意思跟裡面數值代表的意思，這樣取用的時候才知道自己到底抓的是上一次什麼狀態，它是一個「狀態轉移」的過程，概念蠻抽象的，需要多實作幾題透測了解才會有感覺。