---
# System prepended metadata

title: 到底他媽的什麼是動態規劃…

---

# leetcode 332 coin change
前言：此篇文章不是教學文章，是個人筆記，所以不值得拿來學習332，以後會往可以被拿來學習leetcode的方向前進的!!!但目前還是先能做多少做多少~ 畢竟現在是早上2:00~~~~
這題用的是動態規劃的概念，但...
## 到底他媽的什麼是動態規劃
Dynamic Programming = DP
本質：用遞迴關係式，解決大的問題
> 【複習遞迴】
> 例如費式數列
> fib(1)=1
> fib(2)=1
> fib(3) = 
> 

DP：
有最佳子結構、問題會越來越小、還會把曾經算過的子問題的答案記錄起來

參考[這篇文章](https://medium.com/@cutesciuridae/dynamic-programming-%E6%B7%B1%E5%85%A5%E6%B7%BA%E5%87%BA-%E4%BB%A5fibonacci-number-%E7%82%BA%E4%BE%8B-c3fa09e53c5b)
---
1. 定義狀態(我在哪)(?)
2. 定義狀態轉移關係式(我要丟給人家做的事情)
3. 找出base case(遞迴的中止條件)(第一步怎麼走)

舉例來說：
1. 定義狀態：Anne(now) = "19歲女大學生，出生台中，喜歡天空，曾經愛寫程式，但現在覺得被程式打敗"
2. 定義狀態轉移關係式：
    //定義想法: Anne(year) = year歲的我
    //用文字寫遞迴的邏輯：
    Anne(19) = 19歲的我 = 2025/今天日期~2024/MM/DD + Anne(18)
    (我的生日是2005/MM/DD)
    **說明**：
    a. 在這裡，我只要處理今年的我發生什麼事情(例如：「現在覺得被程式打敗」)
    b. 然後剩下的其他事情(為期整整18年的人生)就丟給「其他人」來做
        「其他人」指的是同一個函式：Anne()，但參數不一樣
        eg:Anne(18) = return "曾經愛寫程式" + Anne(17);
        eg:Anne(17) = return "喜歡天空"+Anne(16);
        .....
        
    c. 而且這個參數會越來越小(通常是n-1)，導致最後參數可以達到「base case」
    eg:Anne(0) = if(year == 0){return "在台中出生";}
    
    例如最後將會呼叫：Anne(0), 此時year = 0，被我Anne()裡面的判斷式 if(year == 0)攔截，然後return 我需要的答案：「 19歲女大學生，出生台中，愛打球，曾經愛寫程式，但現在覺得被程式打敗」
    
---
分為兩種做法：
- 遞迴(把每次遞迴的答案記錄起來)
- botton up

要怎麼去想硬幣問題？
## leetcode 332 coin change
> 小小心得...嗚嗚嗚我今天搞她搞了兩個小時多，嗚嗚嗚快不行了，今天是520，要被榨乾了(?
爬了很多文，以下總結
### 硬幣問題題目_by AI翻譯精簡：
[題目連結](https://leetcode.com/problems/coin-change/description/)

🎯 題目描述（精簡版）
你有一組硬幣面額 coins（每種數量無限），和一個目標金額 amount。

請回傳湊出這個金額所需的最少硬幣數量。
若無法湊出，回傳 -1。

✅ 範例：
輸入： coins = [1,2,5], amount = 11
輸出： 3（解釋：5+5+1）

輸入： coins = [2], amount = 3
輸出： -1（無法剛好湊出）

輸入： coins = [1], amount = 0
輸出： 0（不需要任何硬幣）

輸入： coins = [186,419,83,408], amount = 6249
輸出： 20
(這是我爆很久的測資)

### 題目分析
1. 貪心法
2. 遞迴(儲存)
3. botton up


#### 貪心法
我一開始嘗試用：amount=11，先除以最大的數字，再拿餘數除以第二小的數字...

```
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0){
            return 0;
        }
        //int coins = [1, 2, 5];
        //main function
        int result = 0, coin, num;
        for(int i = coins.size()-1 ; i>=0 ; i--){
            coin = coins[i];
            num = amount / coin;
            result +=num;
            amount -= coin*num; //剩下要被拚的錢錢

        }
        if (amount == 0){ //剩餘的錢錢等於零，相當於剛好能用零錢拼湊完成
            return result;
        }
        else{
            return -1;
        }
    }
};




可是不行!!!
因為有些很奇怪的測資
如：coins={1, 3, 4}, amount =6
貪心算法：
    6/4=1...2 
    2/3=0...2 
    2/1=2...0
    =>1+0+2 = 3
人工算法： 3+3，  因為硬幣三元拿兩個


```
✅ 那什麼情況可以用 greedy？
只要硬幣系統滿足某些數學性質，就一定可以用 greedy 解：

✳️ 充分條件（但不必要）：
canonical coin system（標準硬幣系統）

像美金 [1, 5, 10, 25, 50]

每個硬幣值是前面硬幣的倍數

例如 coins = [1, 2, 4, 8, 16]
(by AI)


### 不能用貪心(greedy)，因此我用Dynamic Programming(DP)
以上題為例，DP會：
如：coins={1, 3, 4}, amount =6
設立一個陣列儲存我們算過的東西：
`vector<int> dp`

DP算法： M(6)= min(1+M(6-1), 1+M(6-3), 1+M(6-4))
好吧，然後我寫出來了!!所以就不寫拉，重點都放在下面拉~


```
class Solution {
public:
    int coinChange(vector<int>& coins, int amount){
        //先建立vector 我記得這裡是 vector<int> dp(amount, -1);
        int min, possible_ans;
        vector<int> dp;
        dp.push_back(0); //應該要改成dp[0] = 0//可以去查查為甚麼push_back 不行
        //就botton up 一直從dp[0] 做做做到dp[amount]
        for(int n = 1;n<=amount;n++){
            //做dp[n] eg dp[1]
            //用amount 分別減去c1, c2, c3，去比較i=0~3的 (1+ dp[amount - ci])
            /*設定min初始值*/
            min = -1;
            // min = 很大的數; 
                //或是將min設為不可能的數(-1)，如果判斷式發現min == -1時，
                //就表示這是min第一次被更動，那我就應該直接對min下手，設min = possible_ans

            for(auto c: coins){//這是新學到的方法！ 可以用c去遍歷coins 中的每一個數
                //處理特例：
                //n-c 不能是負的 >=0，dp[n-c]也要有值，不能等於-1
                if(n-c>=0 && dp[n-c] != -1){
                    possible_ans = 1+dp[n-c];
                    if(possible_ans<min || min == -1){
                        min = possible_ans;
                    }
                    //處理特例：
                }

            }
            dp.push_back(min); //挖好漂亮，我就寫min就好，如果他都沒有通過我的檢驗的話min就是-1



        }
        return dp[amount];
    }
};



```
我的筆記：
![13e52c94-0efc-4057-b836-7ecc64ac0352](https://hackmd.io/_uploads/B1_3GS9-xx.jpg)

                                        
### 思考方式：
    先把主架構寫出來，再寫特例，方法就先寫，不一定要一開始寫時就很造架構寫，可以先把變數名稱用簡單的方法想好，例如coins中的一個一個硬幣數值就單單叫c就好。「記住:沒有任何一個人是廢物，所以也沒有任何一個變數是多餘的，要抱持著這樣的想法去寫程式碼」
### 其他
> 今天還學到了可以去點leetcode作答成功畫面，底下柱狀圖，看看其他人拿了多高分，再去看他們的程式碼是怎麼寫的，藉以學習

> 嘗試轉換學習程式的心態：
> 就當作小學時學數學，我們都要老師教一堆奇奇怪怪的算法：雞兔同籠、比較年齡大小...先照老師的方法算，不要求自己第一次看到題目就馬上會寫。
> 題目多看多寫，寫久了...相當於長大了!再回去看我弟的數學題，我就可以很直覺的想說：阿這不就很簡單嗎~我心算就能算出來了，你在不及格什麼
> 以此勉勵自己不要受挫(嗚嗚嗚嗚嗚)



