# Dynamic Programming
###### tags: `Algorithm`
## 概念介紹
1. Divide-and-Conquer Method + Memoization
2. 當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解，以空間換取時間。要先定義dp狀態(資料結構)、找到Transfer function(Sub-problem)
3. 動態規劃的過程，就是反覆地讀取數據、計算數據、儲存數據
4. 為什麼分割問題之後，就容易計算答案呢？因為分割問題時，同時也分類了這個問題的所有可能答案。分類使得答案的規律變得單純，於是更容易求得答案。
5. 方式:
A. Top-down
B. Bottom-up
5. 動態規劃的問題，可以分為「計數問題」和「極值問題」。
A. Matrix
B. Sequence
C. Two Sequences
D. Backpack & Coin Change
ex.在m個大小下能否裝下i個物品、在sum大小下需要最少i個金幣數比較類似計數問題

- Note:
1. 直接用遞迴實作，而不使用記憶體儲存各個問題的答案，是最直接的方式，也是最慢的方式。不斷呼叫同樣的函式求解，效率不彰時間複雜度 O(f(n))。剛接觸 DP 的新手常犯這種錯誤。
2. 節省記憶體是動態規劃當中重要的課題，思考需要儲存的資料為多少 ex.one variable/vector/matrix
3. 如果只打算求出一個問題，那麼只需要儲存最近算出來的問題答案，讓計算過程可以順利進行就可以了。

- Reference:
https://web.ntnu.edu.tw/~algo/DynamicProgramming.html

https://maomaoalgo.gitbook.io/python/hui-su-yu-dong-tai-gui-hua/bei-bao-dp

## DP相關leetcode題目:
https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months

[一些DP pattern整理跟對應的練習題](https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns#distinct-ways)