推 jimmy1112111: 類似01背包問題，背包怎麼做的這個也就類似 12/13 17:53
推 A4P8T6X9: 因為換 M 的問題跟如何換 M-1 本質上是一樣的問題，所 12/13 18:27
→ A4P8T6X9: 以第一題是 M。 12/13 18:27
→ A4P8T6X9: 對 M 來說，他可以測試每一個 M - C_i，來產生最佳解。 12/13 18:28
→ A4P8T6X9: 所以第二題是 d。 12/13 18:28
→ A4P8T6X9: 不過我也是看答案反推的，感覺就是不敢考 code 只能這 12/13 18:30
→ A4P8T6X9: 樣間接考。 12/13 18:30
推 joywilliamjo: 就coin change dp，有a,b,....d種錢幣，是否能湊成1 12/13 19:01
→ joywilliamjo: ,2,3,4.....M元 12/13 19:01
→ joywilliamjo: sub problem:可否湊出1元，2元3元.....m元 12/13 19:02
→ j12345453: 通了謝謝各位！ 12/13 22:57
→ j12345453: 不過第二小題D種選擇 12/13 22:57
→ j12345453: 我稍微懂 但有點不夠清楚 12/13 22:57
→ j12345453: 請問可以再幫我進一步解釋嗎 12/13 22:57
→ j12345453: 我粗略畫了一個DP表格 12/13 23:04
→ j12345453: 我認為螢光筆直行那邊是D種選擇 12/13 23:04
→ j12345453: 橫列是M個子問題 12/13 23:04
→ j12345453: 這樣說得通嗎 12/13 23:04
→ j12345453: 感覺還少了點什麼 12/13 23:04
→ cossetannie: 假設d=2 c1=1 c2=2, dp[i]=min(dp[i-1], dp[i-2])+1 12/13 23:36
→ cossetannie: 就看你d是多少就有幾個sub-problem 12/13 23:37
→ cossetannie: 基本上就可以想成是每次有d種選擇一樣的意思 12/13 23:38