動態規劃 (Dynamic Programming)#
動態規劃是演算法面試中最重要也最具挑戰性的主題。它不僅是一種演算法，更是一種解決問題的思想：利用已經計算好的結果來推導計算，即大規模問題的結果是由小規模問題的結果運算得來的。
為什麼大廠都愛考動態規劃？
- 動態規劃是解決問題的重要方法論，在降低時間複雜度上極具優勢
- 能很好地考察面試者的數學模型抽象能力和邏輯思維能力
- 可以反映個人在演算法上的綜合能力
動態規劃問題的三大類型#
| 類型 | 描述 | 典型問題 |
|---|---|---|
| 求最優解 | 求最大值或最小值 | 背包問題、最長子序列 |
| 求可行性 | 判斷 True/False | 跳躍遊戲、能否湊成目標 |
| 求方案總數 | 計算方案數量 | 路徑規劃、硬幣組合 |
學習建議#
學習動態規劃的正確姿勢
- 先掌握基礎資料結構和演算法（遞迴、搜尋、迭代）
- 重視細節，鍛煉演算法編碼能力
- 掌握經典問題，總結解題思路
- 動態規劃是模板、套路屆的典範，要形成經驗式總結
- 適當刷題，熟能生巧