674: Coin Change ★★☆☆☆ 題組：Problem Set Archive with Online Judge 解題者：莊竺家 解題日期：2019年5月2日 題意：將給定金額(<=7489)轉換成5種硬幣的組合，分別為50分錢、25分錢、10分錢、5分錢、1分錢，最後輸出該金額最多硬幣組合數。(0元只有一種組合方法。)
題意範例： 15 6 //15分錢有6種組合 26 13 //26分錢有13種組合 題意範例： 15 6 //15分錢有6種組合 26 13 //26分錢有13種組合 15分錢的組合 (10)+(5) (10)+(1)*5個 (5)*3個 (5)*2個+(1)*5個 (5)+(1)*10個 (1)*15個 26分錢的組合 (25)+(1) (10)*2+(5)+(1) (10)*2+ (1)*6 (10)+(5)*3+(1) (10)+(5)*2+(1)*6 (10)+(5) +(1)*11 (10)+(1)*16 (5)*5+(1) (5)*4+(1)*6 (5)*3+(1)*11 (5)*2+(1)*16 (5)+(1)*21 (1)*26
15分錢=14分錢+(1)=10分錢+(5)=5分錢+(10) 15分錢的硬幣組合數=14分錢的組合數+10分錢的組合數+5分錢的組合數 解法：用暴力法建出組合數表再查表 解法範例： 15分錢=14分錢+(1)=10分錢+(5)=5分錢+(10) 15分錢的硬幣組合數=14分錢的組合數+10分錢的組合數+5分錢的組合數 先從(1)分錢開始討論： 15分錢=14分錢+(1)=13分錢+(1)*2=… =0分錢+(1)*15 w[0]=1 w[0+1]+=w[0] w[1+1]+=w[1] w[2+1]+=w[2] w[3+1]+=w[3] w[4+1]+=w[4] w[5+1]+=w[5] w[6+1]+=w[6] w[7+1]+=w[7] w[8+1]+=w[8] w[9+1]+=w[9] w[10+1]+=w[10] w[11+1]+=w[11] w[12+1]+=w[12] w[13+1]+=w[13] w[14+1]+=w[14] w[0]=1 w[1] =1 w[2]=1 w[3] =1 w[4] =1 w[5]=1 w[6] =1 w[7] =1 w[8] =1 w[9] =1 w[10] =1 w[11] =1 w[12] =1 w[13]=1 w[14] =1 w[15]=1
討論(5)分錢： 10分錢+(5)=5分錢+(5)*2=0分錢+(5)*3 w[0]=1 w[0+5]+=w[0] w[1+5]+=w[1]
直覺會想每次只處理該數，但每次都要跑很多次迴圈(講義1-22~1-31)，其實只要建好一次表就能用無限多次了。 討論(10)分錢： 5分錢+(10) 15分錢有6種表示方法 討論： 直覺會想每次只處理該數，但每次都要跑很多次迴圈(講義1-22~1-31)，其實只要建好一次表就能用無限多次了。 w[0]=1 w[0+10]+=w[0] w[1+10]+=w[1] w[2+10]+=w[2] w[3+10]+=w[3] w[4+10]+=w[4] w[5+10]+=w[5] w[6+10]+=w[6] w[7+10]+=w[7] w[8+10]+=w[8] w[9+10]+=w[9] w[10+10]+=w[10] w[11+10]+=w[11] w[12+10]+=w[12] w[13+10]+=w[13] w[14+10]+=w[14] w[0]=1 w[1] =1 w[2]=1 w[3] =1 w[4] =1 w[5]=2 w[6] =2 w[7] =2 w[8] =2 w[9] =2 w[10] =3+1=4 w[11] =3+1=4 w[12] =3+1=4 w[13]=3+1=4 w[14] =3+1=4 w[15]=4+2=6