---
# System prepended metadata

title: 1.2 Dynamic Programming Framework

---

# 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];
}
~~~