https://i.imgur.com/AFM2trb.jpg
想請問各位大佬
題35
a b問題的解答是怎麼來的呢

類似01背包問題，背包怎麼做的這個也就類似

因為換 M 的問題跟如何換 M-1 本質上是一樣的問題，所以第一題是 M。對 M 來說，他可以測試每一個 M - C_i，來產生最佳解。所以第二題是 d。不過我也是看答案反推的，感覺就是不敢考 code 只能這樣間接考。

就coin change dp，有a,b,....d種錢幣，是否能湊成1,2,3,4.....M元sub problem:可否湊出1元，2元3元.....m元

通了謝謝各位！不過第二小題D種選擇我稍微懂 但有點不夠清楚請問可以再幫我進一步解釋嗎https://i.imgur.com/uWCdyxI.jpg我粗略畫了一個DP表格我認為螢光筆直行那邊是D種選擇橫列是M個子問題這樣說得通嗎感覺還少了點什麼

假設d=2 c1=1 c2=2, dp[i]=min(dp[i-1], dp[i-2])+1就看你d是多少就有幾個sub-problem基本上就可以想成是每次有d種選擇一樣的意思