# 1.2 Dynamic Programming Framework
## 1.2.0 intro:
- 一般形式: 求極值
- 核心問題: 列舉
- 思考如何列舉所有結果
- 存在"重疊子問題" (Overlapping sub-problems)--> Memo
- 具備"最佳子結構" (optimal sub-structure)
- 列出正確的"狀態轉移方程"-->state transfer function, most difficult
- 思考要點:
- base case (最簡單的情況)是什麼?
- 這個問題有什麼"狀態"?
- 對於每個"狀態"，可以做出什麼"選擇"，使得"狀態"發生改變?
- 如何定義dp陣列/函數的涵義，以便表現"狀態"和"選擇"?
- 三點: 狀態、選擇、dp陣列的定義

~~~
# initialize base case
dp[0][0][...] = base case

for state1 in all possible:
for state 2 in all possible:
dp[state1][state2] = max/min(option 1, option 2)

~~~

## 1.2.1 Fib sequence for overlapping sub-problems
~~~
int fib(int N){
if (N==0) return 0;
if (N==1 || N==2) return 1:
return fib(N-1)+ fib(N-2);
}
~~~

- Complexity of Recursive = # of sub-problems x complexity of sub-problem
- Fib (Brute Force) : O($2^n$)
- DP Optimization for overlapping sub-problems:
- First, write a brute-force version (include state transfer function)
- Choose method:
- Memo (Top-down)
- dp table: (Bottom-up)
- (Advanced) State compressiong: Based on state-transfer-function, there might be method to reduce dp table to save spce complexity.

## 1.2.2 Coin change: State transfer function (optimal sub-structure)
- Problem: given k types of coins (c1,c2,...,ck), and target amount-->min # of coins
- Steps:
- Base case: amount = 0--> return 0
- 確定"State": 原本問題與子問題的變數(e.g., amount)
- 確定"選擇": 導致狀態改變的行為
- 明確dp: 函數/ 陣列定義
- dp"函數"的狀態體現於"函數參數"
- dp"陣列"的狀態體現於"陣列索引"
- Top Down (Memo)
~~~ python
def coinChange(self, coins, amount):
memo = dict()
def dp(n):
# Memo
if n in memo: return memo[n]

# base case
if n==0: return 0
if n<0: return -1
res = float('INF')

# state transfer
for coin in coins:
subproblem = dp(n-coin)
if subproblem==-1: continue

res = min(res, 1+subproblem)

# add into memo
memo[n]= res if res!=float('INF') else -1
return memo[n]

return dp(amount)
~~~

- Bottom Up (DP table)
~~~C++
int coinChange(vector<int>& coins, int amount){

// size of array = amount+1
// initialized value = amount +1 (like an infinite value)
vector<int> dp(amount+1, amount+1);
// base case
dp[0]=0;

// for All the states
for(int i = 0;i<dp.size();i++){
// for all the options
for(int coin : coins){

// if sub-problem is not sovlable, by pass it.
if (i-coin<0) continue;

// solve sub-problem.
dp[i]=min(dp[i], 1+dp[i-coin]);
}
}
return (dp[amount]==amount+1)? -1: dp[amount];
}
~~~