此演算法是分治法的延伸，將一個問題分成好幾個小問題，並將小問題解出並記錄答案，例如用一個陣列去儲存，這些小問題的答案就不用被重複計算，最後根據小問題的答案取得整個問題的答案，DP 也常搭配遞迴使用。

所以 DP 的重點在: 拆分(divide & conquer)和儲存(memoization)。

適合使用的問題要包括兩個條件:

1. optimal substructure: 子問題與原問題的求解方式皆類似，例如最短路徑
2. overlapping subproblems: 一個問題可以被分解成多個子問題，且問題的結果可以被記憶儲存多次使用，例如費伯那西數列

動態規劃的解題步驟：

1. 根據重複子問題定義狀態
2. 尋找最優子結構，推導狀態轉移方程
3. 確定 DP 初始狀態
4. 確定輸出值

動規例子:

1. 費氏數列，詳細分析可以參考我以前鐵人賽寫的文章: https://ithelp.ithome.com.tw/articles/10296046
2. 0/1背包問題
3. LeetCode Climbing Stairs

以下就用 LeetCode Climbing Stairs 這個題目來看看怎麼應用動態規劃。

這題如果經過觀察會發現，如果是 4 階階梯會有 5 種走法，5 階階梯會有 8 種走法，剛好很像費氏數列一樣，當前的結果(n 階階梯)是前兩個結果(n - 1 階階梯)加上(n - 2 階階梯)的總和。

所以正好可以利用到動態規劃的概念，去儲存之前計算的結果再組合出最終要取得的答案。

所以就是跑迴圈，每上升一階時(i + 1)就增加當前 i 階的走法數量到儲存結果的 stepResults 陣列。

var climbStairs = function(n) {
  const stepResults = [0, 1, 2];
  
  for (let i = 2; i < n; i++) {
    stepResults.push(stepResults[stepResults.length - 1] + stepResults[stepResults.length - 2]);
  }
  return stepResults[n];
};

動態規劃、貪婪演算法、回溯法的區別

• 動態規劃: 記錄局部最佳解，有回退功能
• 貪婪演算法: 求局部最優，無回退功能
• 回溯法: 大量的重複計算來獲得最佳解