Dynamic Programming

動態規劃（Dynamic Programming，簡稱 DP）是一種 **「把大問題拆成小問題，並把算過的答案記下來」*- 的技巧。

例如銀行帳戶初始餘額是 0，但每次都記錄上一次交易後的餘額，這樣就不用每次查看餘額都須從初始狀態開始算。

這種「用空間換取時間」的方法，可以讓原本要算很久的題目，在幾秒鐘內就解出來。

核心兩大特徵

如果一個問題可以用 DP 來解，它通常會符合以下兩個特色：

• 重疊子問題（Overlapping Sub-problems）：大問題拆開後，會重複出現一模一樣的小問題
• 最佳子結構（Optimal Substructure）：小問題的最佳答案，可以組合成大問題的最佳答案

範例

費氏數列（Fibonacci）是解釋 DP 的經典例題，可參考 Leetcode 題目。

題目：費氏數列的規則是後面的數字等於前面兩個數字相加（1, 1, 2, 3, 5, 8...），算出第 n 個數字為多少。

Example 1:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 2:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

暴力解

var fib = function(n) {
    if (n <= 1) return n
    return fib(n-1) + fib(n-2)
};

Time Complexity: O(2^n) Space Complexity: O(n)

如果是要算第 4 個數字，則會拆成：

                  fib(4)
                 /      \
           fib(3)        fib(2)
          /      \       /     \
      fib(2)   fib(1)  fib(1)  fib(0)
     /      \
 fib(1)   fib(0)

其中

• fib(2) 被完整計算了 2 次。
• fib(1) 被完整計算了 3 次。

重複計算都是額外消耗時間。

DP 解

費氏數列的定義：後面的數字等於前面兩個數字相加 f(n) = f(n-1) + f(n-2)

滿足可用 DP 的特徵：

• 重疊子問題（Overlapping Sub-problems）：大問題拆開後，會重複出現一模一樣的小問題
• 最佳子結構（Optimal Substructure）：小問題的最佳答案，可以組合成大問題的最佳答案

因此，只需多加一個變數以儲存已經處理過的問題，之後再有需要即可直接存取。

var fib = function(n) {
    if (n <= 1) return n
    const memo = [0, 1] // 儲存計算過的內容
    
    for (let i = 2; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2]
    }
    
    return memo[n]
};