動態規劃 (Dynamic Programming)#

動態規劃是演算法面試中最重要也最具挑戰性的主題。它不僅是一種演算法，更是一種解決問題的思想：利用已經計算好的結果來推導計算，即大規模問題的結果是由小規模問題的結果運算得來的。

為什麼大廠都愛考動態規劃？

  • 動態規劃是解決問題的重要方法論，在降低時間複雜度上極具優勢
  • 能很好地考察面試者的數學模型抽象能力和邏輯思維能力
  • 可以反映個人在演算法上的綜合能力

本章內容#

本章將從貪心演算法開始，逐步引導你理解動態規劃的本質，並掌握常見的 DP 問題類型：

  1. 動態規劃入門 - 從硬幣找零問題認識貪心演算法的局限性
  2. 從暴力到 DP - 遞迴、備忘錄到動態規劃的演進
  3. DP 三要素 - 重叠子問題、無後效性、最優子結構
  4. 背包問題 - 0-1 背包與完全背包詳解
  5. 子陣列與子序列 - 兩大經典問題類型
  6. 經典 DP 問題 - 爬樓梯、零錢兌換、編輯距離
  7. 股票交易系列 - 多狀態 DP 的典範
  8. DP 實戰指南 - 刷題策略與總結

動態規劃問題的三大類型#

類型描述典型問題
求最優解求最大值或最小值背包問題、最長子序列
求可行性判斷 True/False跳躍遊戲、能否湊成目標
求方案總數計算方案數量路徑規劃、硬幣組合

學習建議#

學習動態規劃的正確姿勢

  1. 先掌握基礎資料結構和演算法（遞迴、搜尋、迭代）
  2. 重視細節，鍛煉演算法編碼能力
  3. 掌握經典問題，總結解題思路
  4. 動態規劃是模板、套路屆的典範，要形成經驗式總結
  5. 適當刷題，熟能生巧
Backward 經典問題 動態規劃入門 Forward