成大演算法CoinChange

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