# 動態規劃 (Dynamic programming)

## 解題步驟

1. 窮舉分析
2. 找出邊界
3. 找出規律、拆分子問題
4. 寫出狀態轉移方程
5. 找出狀態壓縮規律，達成空間複雜度最優解

## 動態規劃的種類

動態規劃大致上可以分成兩種不同類型的動態規劃：

### 一維動態規劃

顧名思義，一維動態規劃主要專注在平面維度空間複雜度的動態規劃問題，通常以 Array 的 DP 最為大宗，大部分問題的空間複雜度都可狀態壓縮至常數級別 O(1)

### 多維動態規劃

多維動態規劃會涉及到 Matrix、Array 等等問題，通常多維動態規劃指的是需要使用多維空間複雜度來解決的動態規劃問題，大部分問題的空間複雜度可狀態壓縮至一維級別的空間 O(n)，少部分問題可利用解答把空間複雜度將至 O(1)

## 參考資料

- [理解動態規劃](https://zhuanlan.zhihu.com/p/367338880)
- [五大基本算法之动态规划算法 DP dynamic programming](https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp)