蘇世機(jī)試小課堂，考研機(jī)試不再慌！

最小郵票數(shù)

題目描述

有若干張郵票，要求從中選取最少的郵票張數(shù)湊成一個(gè)給定的總值。如，有1分，3分，3分，3分，4分五張郵票，要求湊成10分，則使用3張郵票：3分、3分、4分即可。

輸入描述

有多組數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，首先是要求湊成的郵票總值M，M<100。然后是一個(gè)數(shù)N，N〈20，表示有N張郵票。接下來是N個(gè)正整數(shù)，分別表示這N張郵票的面值，且以升序排列。

輸出描述

對(duì)于每組數(shù)據(jù)，能夠湊成總值M的最少郵票張數(shù)。若無解，輸出0。

輸入?

10

5

1 3 3 3 4

輸出

3

答案

①讀題:

題意很明顯，就是選擇最少的郵票數(shù)湊成給定的總值。

②想出思路：

要求解和一致情況下的組合數(shù)最小，這里定義一個(gè)dp數(shù)組存放結(jié)果值，雙重循環(huán)遍歷郵票張數(shù)，第二層從n開始遞減到a[i],逐漸找到最小，最后輸出結(jié)果位

③動(dòng)手編程：

④測(cè)試樣例：

⑤提交代碼：

進(jìn)入下面的鏈接提交代碼：

https://www.nowcoder.com/practice/83800ae3292b4256b7349ded5f178dd1?tpId=40&&tqId=21345&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回評(píng)測(cè)結(jié)果：

至此，這道題我們就已經(jīng)完成了。

本題總結(jié)

動(dòng)態(tài)規(guī)劃典型題目，最重要的是明白兩層for循環(huán)為什么這么寫。

蘇世學(xué)社旗下品牌，專注于計(jì)算機(jī)考研

計(jì)算機(jī)考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學(xué)習(xí)分享丨咨詢前輩丨個(gè)性化指導(dǎo)