動態規劃的核心思路是:將一個大問題拆分成若干個性質相似的小問題，解決並記住小問題的答案，以此推導出大問題的答案。

實例講解

一個有5個階梯的樓梯，每次只能走1階或2階，總共有幾種走法?

思考技巧:不要從第1階思考共有幾種排列組合能走到最後一階，而是用到達最後一階只有幾種可能

走到第五階只能從第四階或第三階走過去，因此【爬到第5階】的組合數量就是【爬到第4階】的組合數量 + 【爬到第3階】的組合數量。

因此類推

• 【爬到第4階】的組合數量 就是 【爬到第3階】的組合數量 + 【爬到第2階】的組合數量
• 【爬到第3階】的組合數量 就是 【爬到第2階】的組合數量 + 【爬到第1階】的組合數量

這樣推導出來的公式為

f(n) = f(n-1) + f(n-2)

f(5) 
├── f(4) 
│ ├── f(3) 
│ │ ├── f(2)
│ │ └── f(1) 
│ └── f(2) ← 重複計算！ 
└── f(3) ← 重複計算！ 
├── f(2) ← 重複計算！ 
└── f(1) ← 重複計算！

動態規劃的使用時機

1. 重疊的小問題

以爬樓梯為例，f(5)是大問題，拆分成f(4)、f(3)、f(2)等小問題

2. 目標是找到最大問題的最優解

大問題的解答是由小問題答案推導出來的，所以小問題的最優解相對是大問題的最優解

兩種遍歷動態規劃的方式

1. Top-Down (記憶化搜尋)

從最大的問題開始向下遞迴。

遞迴時遇到沒有解過的小問題時，先計算出該問題的解答並紀錄暫時性的表格，等下次遇到同樣性質的小問題時直接查表找答案。

但這種方法會造成空間複雜度上升，使用時要注意

def climbStairs(n:int, memo=[]) ->int:
    if n <= 1:
        return 1

    if n in memo:
        return memo[n]

    memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo)

    return memo[n]

2. Bottom-Up

先解決最小的問題，遞迴向上推導出大問題的解答。

def climbStairs(n:int) ->int:
    if n <= 1:
        return 1

    dp = [0] * (n-1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n+1, 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]