作者j12345453 (CJentalL)
看板Grad-ProbAsk
標題成大演算法CoinChange
時間Mon Dec 13 17:02:17 2021
https://i.imgur.com/AFM2trb.jpg
想請問各位大佬
題35
a b問題的解答是怎麼來的呢
----
Sent from
BePTT on my iPhone 11
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.52.92 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1639386139.A.C60.html
1F：推 jimmy1112111: 類似01背包問題，背包怎麼做的這個也就類似 12/13 17:53
2F：推 A4P8T6X9: 因為換 M 的問題跟如何換 M-1 本質上是一樣的問題，所 12/13 18:27
3F：→ A4P8T6X9: 以第一題是 M。 12/13 18:27
4F：→ A4P8T6X9: 對 M 來說，他可以測試每一個 M - C_i，來產生最佳解。 12/13 18:28
5F：→ A4P8T6X9: 所以第二題是 d。 12/13 18:28
6F：→ A4P8T6X9: 不過我也是看答案反推的，感覺就是不敢考 code 只能這 12/13 18:30
7F：→ A4P8T6X9: 樣間接考。 12/13 18:30
8F：推 joywilliamjo: 就coin change dp，有a,b,....d種錢幣，是否能湊成1 12/13 19:01
9F：→ joywilliamjo: ,2,3,4.....M元 12/13 19:01
10F：→ joywilliamjo: sub problem:可否湊出1元，2元3元.....m元 12/13 19:02
11F：→ j12345453: 通了謝謝各位！ 12/13 22:57
12F：→ j12345453: 不過第二小題D種選擇 12/13 22:57
13F：→ j12345453: 我稍微懂 但有點不夠清楚 12/13 22:57
14F：→ j12345453: 請問可以再幫我進一步解釋嗎 12/13 22:57
16F：→ j12345453: 我粗略畫了一個DP表格 12/13 23:04
17F：→ j12345453: 我認為螢光筆直行那邊是D種選擇 12/13 23:04
18F：→ j12345453: 橫列是M個子問題 12/13 23:04
19F：→ j12345453: 這樣說得通嗎 12/13 23:04
20F：→ j12345453: 感覺還少了點什麼 12/13 23:04
21F：→ cossetannie: 假設d=2 c1=1 c2=2, dp[i]=min(dp[i-1], dp[i-2])+1 12/13 23:36
22F：→ cossetannie: 就看你d是多少就有幾個sub-problem 12/13 23:37
23F：→ cossetannie: 基本上就可以想成是每次有d種選擇一樣的意思 12/13 23:38