這一段我們著重在「動態規劃」優化，如何從窮舉或遞迴的方法中進一步地將結果記錄下來而不用重複計算。例如昨天的「爬第 n 階樓梯的方法數」與今天的「移動到 m, n 格子的路徑數」，都是可以同時使用到「遞迴」與「動態規劃」兩種解法。我們也挑選了三題有趣的問題一起體驗了這個過程，逐步從「窮舉」→「遞迴」→「動態規劃」的練習與嘗試優化。
方法 ① 直覺先用窮舉法（兩層迴圈）計算符合題目要求的所有可能值將最大的那一組留下來，不過實際上跑測資時不意外的出現 Time Limit Exceeded 的錯誤。方法 ② 從觀察窮舉法開始，找出計算過程中可以優化的空間與解法，只要將每次都從頭開始改成每回合累加前一回合的結果，這種方法稱為貪婪法（Greedy）。第三種方法更一步將累加的過程直接暫存到另一個變數中，把所有可能的結果用「空間」換取「時間」，其實就是動態規劃（Dynamic Programming）的基本思路。
延續著動態規劃的想法，我們下一題選得「爬樓梯」這道是經典的動態規劃題。從這個題目的規則中很直覺的會想到用地遞迴的方式解題，有一個很明確的迭代過程跟規則。只是遞迴在這裡會遇到時間跟效能上的議題，所以用「空間」換取「時間」來處理，將原本的遞迴解法轉換成動態規劃的方式來解。這裡大概會有一個小小的筆記，就是關於「暫存」的問大概可以聯想到「資料結構」或「遞迴」的方法來優化，而「遞迴」又可以與「動態規劃」相互轉換。
第三天用 Unique Paths 題目作為是動態規劃的小結，這兩天的題目都在嘗試動態規劃的問題，逐步從「窮舉」→「遞迴」→「動態規劃」的練習與優化過程，其實會發現「動態規劃」跟「遞迴」根本只有一線之隔，搞懂了遞迴、動態規劃就是把用「空間」換取「時間」的轉換。
貪婪演算法（Greedy algorithm）是指在求解問題時，在每一個步驟中選擇「當下最好的結果/解法」，而不一定會考慮到該解法對最終解的影響。換句話說，貪婪法能考慮到的是區域最佳解（Local Optimization），不代表會同時滿足全域最佳解（Global Optimization）。
▇ 常見的貪婪演算法
動態規劃（Dynamic Programming）會將一個大的問題轉換成由較小的問題組合而成，透過先處理較小問題並將結果暫存起來，透過小問題的暫存結果再進一步建構出原始問題的可行解。
▇ 常見的動態規劃法
動態規劃其實是分治法（Divide-and-Conquer）的一種延伸與特例，分治法採用由上而下（top-down）的解題思路 方式，可將原始問題分成多個小的，而所有小問題的結果彙整合併（bottom-up）由下而上，之後就可以成為原始問題的最終解法。根據相同的邏輯，動態規劃跟遞迴其實都可以算是分治法的一種實現。
▇ 常見的分治法
雖然我們說動態規劃是一種分治法的延伸，不過如果硬要比較的話可以這樣理解。適合動態規劃法的題目，通常從原始問題中定義出的問題不是相互獨立的，所以我們需要利用現有或新建立變數來暫存所有小問題的結果（不管會不會被用到，都需要將結果記錄下來）。
嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。
iThome鐵人賽
看影片追技術