來到了我們三十天演算法的最後一個章節，動態規劃。
動態規劃留了三天給他，希望能多看一點題目。
動態規劃老實說概念不難，但如何知道是動態規劃後按邏輯寫出動態規劃思維的程式碼，並不是一件簡單的事(動態規劃在 Leetcode 上這個 tag 底下應該不少 Hard 的題目)。
寫出來的程式碼可能大相逕庭，儘管核心都是動態規劃，動態規劃的程式碼寫起來通常也不會到非常複雜，複雜的是背後的思維。
說了這麼多讓人心癢的話，讓我們直接來開始認識動態規劃吧。

動態規劃是什麼

動態規劃解決的問題一般是求最值問題，即最長、最短、最大、最小，連續值後的某個累加值應該為多少。
求最值問題的基本方法就是窮舉，畢竟要確認該值為最，除了特定排序的情況下外，可行的值都要列出來比較。暴力的去寫窮舉一般不難，可是是件耗資源的事，舉著舉著不是超時就是記憶體不夠 ─ 如何聰明的窮舉就很重要了，透過備忘錄結構來儲存已計算過的結果、避免重複的計算，讓程式碼能在限制的時間空間下完成問題。

動態規劃與貪心算法

動態規劃核心概念在於每一個狀態(值)，都是由關聯的狀態推導出來的，可能是從前往後、從後往前，這個關聯在於題目指示的線索。
這點也是和前文剛提過的貪心算法最大差異：貪心算法僅專注目前選項，無論過去選項、未來選項如何，走過不回頭，並不會因為過去的問題更新的值，或現在的選擇調整，影響下一次的選擇條件。動態規劃選擇間是有關的，在挑選一個選擇後，以此選擇為基準，不斷更新以得出最佳選擇。
這邊盡量不導入比較複雜的術語，做幾題後應該能比較清晰的分辨動態規劃和貪心算法的不同。

動態規劃基本步驟

動態規劃的解題概要是這樣的，如上所述動態規劃的問題都會有一個核心的算法，很多人解題的時候會把相關的陣列 / 儲存物件命名為 dp(Dynamic Programming)。
dp[i] = dp[i-1] + dp[i-2]
像這樣的方程式我們稱作狀態轉移方程式，也是動態規劃裡面的核心。
狀態一詞可以理解為問題關聯參數，也就是核心問題想求的那個最值的大小變化。

1. 首先，我們需要先定義問題中核心要求的數 - 確認狀態
2. 了解該問題的關聯(遞增 / 遞減，挑選的邏輯) - 確認選擇(邏輯)
3. 透過 1 與 2 的分析，去推出狀態轉移方程式，決定目標狀態如何被推導出來、下標涵義
4. 狀態推導公式一般會需要基礎狀態才能夠開始不斷推導，確立初始值(如上面的狀態，)
5. 確認於連續事件中狀態轉移方程式對資料源的遍歷方向(從前往後、從後往前、矩陣上到下...等等)
6. 驗證推導結果，確定初始值

動態規劃的說明，一般都會以斐波那契數列來講解狀態轉移方程式的概念，但因為它並不是一個求最值的問題，嚴格來說和動態規劃只能說有概念相同，但並不太算是動態規劃。
斐波那契數列是一個第三項為前兩項相加的總和，上面寫出的 dp[i] = dp[i-1] + dp[i-2] 就是在描述這件事。
所以如果用這個概念來做一次步驟展示，就會像這樣：

1. 所求狀態就是要求數列中的第 n 個值
2. 這題沒有選擇的邏輯在
3. 我們做出的 dp[i] 代表斐波那契數列中的第 i 個值，狀態轉移方程式就是 dp[i] = dp[i-1] + dp[i-2]
4. 在陣列的概念裡，可以想見 i 必須從 2 開始(使得 i - 2 >= 0)，所以我們需要定一 dp[0] 和 dp[1]，在斐波那契數列中，這兩個值皆為 1
5. 斐波那契數列的遍歷方向單純，就是從前往後疊加
6. 所以照這個推理我們就能得出 dp[2] = dp[1] + dp[0] => 1 + 1 = 2，dp[2] = 2，類推 dp[3] = 3 ...，可以確認是符合斐波那契數列的規律

還能夠看到一個點是所謂的「重複子問題」，這也是讓我們意識到應該使用動態規劃的一個暗示。
什麼叫重複子問題？舉例，斐波那契數列的第 5 個數，會是第 4 個加第 3 個，要求出第 4 個和第 3 個，則會分別是第 2 個加第 3 個加上第 1 個加上第 2 個。
可以發現在得出現在這個值之前，我們需要大量重複的計算，我們完全可以用一個備忘錄(dictionary / array)去把曾經計算過的數值存起，節省再次計算的時間。

Min Cost Climbing Stairs

那我們今天至少來看一題，比較基本的動態規劃，感受一下時機的概念：爬梯子問題。
問題是這樣的，給你一個整數陣列 cost，下標代表第 i 格，裡面包含著從這格移動的話，需要花費多少力氣。
每次移動可以移動 1 或 2 格，花費的力氣一樣(看從哪格移動)。
一開始我們可以選擇要把第 0 格或第 1 格當作起點，這個起點的選擇是不花費力氣的。
回傳爬到頂端的所需花費的最小力氣，頂端是指陣列的長度 + 1(即會從最後一格走一步或倒數第二格走兩步離開陣列)。

我們一樣用上面列出的步驟來展示。

1. 問題要解出最小的力氣，力氣在離開該格時花費，無論移動一格或兩格都一樣
2. 選擇的邏輯就是要選到第 i 格花費最小力氣的
3. 我們定義 dp[i] 為走到第 i 格花費的最小力氣。因為每次可以移動一格或兩格，我們可以知道，這格必定是由前兩格其中一個走過來，從花費比較小力氣的那個路線走過來，透過這個敘述，我們可以得到：
   dp[i] = Math.Min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]
   這邊的 dp[i-1] 表示到第 i - 1 格所花費的最小力氣，加 cost[i-1] 從該格離開所花費的力氣，就是我們上面的描述，加上和 i - 2 格的數值比較
4. 一樣，我們的初始必須得到的會是 dp[0] 和 dp[1]，這邊要注意的是，我們一開始就可以選擇在第 0 或 1 格出發，而這個選擇是不花費力氣的，也就是 dp[0] 和 dp[1] 都會是 0
5. 樓梯從低到高，我們從前到後遍歷這個 cost 陣列同時更新 dp 陣列即可
6. dp 陣列的長度會是 cost.Length + 1(因為我們的終點定義是爬完整個陣列)，可以嘗試印出前幾個確認(驗證我們的邏輯是否正確)

程式碼如下，一般動態規劃的程式碼都相對簡單，但想清楚整個問題並不容易，需要把問題描述搞清晰後，好好定義一番才能夠理的清邏輯。

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        var dp = new int[cost.Length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(var i = 2; i < dp.Length; i++){
            dp[i] = Math.Min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[cost.Length];
    }
}

今天先用簡單的一道題目做開場，再來兩天，我們會繼續這樣看更多的動態規劃相關問題。