不知不覺就到Day 29了! 老實說我還沒想到明天要寫什麼主題
那麼今天一樣延續這幾天演算法的介紹
前面我們學過遞迴(Recursion)、分治法(Divide and Conquer) (在Merge Sort提過)以及貪心演算法(Greedy)，今天要來介紹演算法中非常重要的一個part 動態規劃(Dynamic Programming, DP)。

什麼是動態規劃？

動態規劃簡單來說是「把大問題拆成小問題」，「然後為了避免重複計算小問題，而將答案記錄下來」

動態規劃適用的問題通常具有以下特性

• 最佳子結構（Optimal Substructure）：問題的最佳解包含其子問題的最佳解，例如 fib(5) 等於 fib(4)+fib(3)

• 重疊子問題（Overlapping Subproblems）：在求解過程中，相同的子問題會被反覆計算。

但上面的把大問題拆成小問題是不是感覺在哪裡看過？
其實在Day 5有介紹過遞迴，可以回去複習一下 !

那還記得我們在Day 3時曾題過費波那契遞迴的時間複雜度是O(2ⁿ)嗎?

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

我們那時候有說，假設要算 fib(5)

fib(5)
= fib(4) + fib(3)

fib(4)
= fib(3) + fib(2)

fib(3)
= fib(2) + fib(1)

fib(2)
= fib(1) + fib(0)

可以發現fib(3)被計算不只一次，然後fib(2)被算了更多次，有許多子問題被重複計算
因此時間複雜度高達：O(2^n)

記憶化(memoization)

既然會重複計算，我們可以把結果存起來，這樣下次要用直接查就好 !

vector<int> memo(100, -1);

建立一個Memo ，初始化長度為 100，所有元素填入 -1
-1 代表這個 n 的答案尚未被計算過

下列寫法稱為由上而下(Top-Down) : 從大問題出發，遇到還沒算過的子問題才計算

vector<int> memo(100, -1);
int fib(int n) {
    if (n <= 1){ //base case
        return n;
    } 
    if (memo[n] != -1){ 
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n]; 
}

時間複雜度 : O(n)

Bottom-Up

從小問題開始往上計算，不使用遞迴

int fib(int n) { 
    if (n <= 1) return n;
    vector<int> dp(n + 1); //宣告大小為 n + 1 的陣列
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n]; 
}

用一個陣列 dp，依序從 dp[0]、dp[1] 開始，一路往上算到 dp[n]，每一步都只用到前面已經算好的結果
並且這方法不會用到遞迴，所以也沒有我們之前提過的 Call stack，
通常會更節省空間

時間複雜度 : O(n)

DP 與遞迴的差異

那麼我們明天繼續加油!

參考資料和書籍

1. https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-dynamic-programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83-de980ca4a2d3
2. https://www.hello-algo.com/zh-hant/chapter_dynamic_programming/intro_to_dynamic_programming/