本週規劃

第一週:Array
第二週:Hash Table
第三週:Dynamic Programming

1. Climbing Stairs (Easy)
2. Fibonacci Number (Easy)
3. House Robber (Medium)
4. Coin Change (Medium)
5. Longest Increasing Subsequence (Medium)
6. Unique Paths (Medium)
7. Edit Distance (Hard)

第四週:Graph

Dynamic Programming

那麼在進入第三週的解題前，我們先來認識一下Dynamic Programming吧!
Dynamic Programming是動態規劃，又簡稱為DP，他是一種透過拆解問題來解決整個問題的一種演算法設計技巧。它的核心在於每一個狀態都是由與其他已知的狀態推導出來的，這個關連可能是由前往後、由後往前或是雙向的，那他們的關聯就要從題目的條件和線索去推導。
那他常常被使用的情況有:

• 序列型（Sequence DP):處理字串、陣列、子序列相關問題。ex:Fibonacci 數列、編輯距離
• 背包型（Knapsack DP):處理「選擇問題」，怎樣才能最佳化。ex:硬幣兌換
• 區間型(Interval DP):處理「區間分割」及「合併」問題。ex:括號合法性判斷

遞迴（Recursion）

Fibonacci 數列：
F(n) = F(n-1) + F(n-2)

陣列與索引

陣列dp[i]來記錄子問題的答案。
例如:dp[i] = 到第i階樓梯的最小花費。

數學歸納法

DP的遞推式就是「下一步依賴前一步」，每一步都有關聯。
最常見的就是:
線性遞推：dp[i] = dp[i-1] + dp[i-2]
選擇最小/最大：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

狀態轉移（State Transition）

他是最核心的公式，定義了「狀態」+「轉移規則」。
例如:dp[i] = dp[i-1] + dp[i-2]
(到第 i 階的方法數 = 到 i-1 階的方法數 + 到 i-2 階的方法數)

時間空間優化

DP 常見空間優化：只需要前兩個狀態時，就用兩個變數代替整個陣列。

參考資料: