# 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];
}
};
```
我的筆記：
### 思考方式：
先把主架構寫出來，再寫特例，方法就先寫，不一定要一開始寫時就很造架構寫，可以先把變數名稱用簡單的方法想好，例如coins中的一個一個硬幣數值就單單叫c就好。「記住:沒有任何一個人是廢物，所以也沒有任何一個變數是多餘的，要抱持著這樣的想法去寫程式碼」
### 其他
> 今天還學到了可以去點leetcode作答成功畫面，底下柱狀圖，看看其他人拿了多高分，再去看他們的程式碼是怎麼寫的，藉以學習
> 嘗試轉換學習程式的心態：
> 就當作小學時學數學，我們都要老師教一堆奇奇怪怪的算法：雞兔同籠、比較年齡大小...先照老師的方法算，不要求自己第一次看到題目就馬上會寫。
> 題目多看多寫，寫久了...相當於長大了!再回去看我弟的數學題，我就可以很直覺的想說：阿這不就很簡單嗎~我心算就能算出來了，你在不及格什麼
> 以此勉勵自己不要受挫(嗚嗚嗚嗚嗚)
Sign in with Wallet
Connect another wallet