題目描述：
這題和做題昨天類似，區(qū)別在于它是需要用最小的 錢的組合去打成目標(biāo)金額
舉個(gè)栗子：
輸入：目標(biāo)金額 6 和 面額數(shù)組[ 1, 2, 4 ]
我們需要用最少的面額組合去達(dá)成這個(gè)目標(biāo)金額，所以就不能像上一題一樣，使用6個(gè)一塊錢，那就不是最小硬幣使用了。我們最佳的組合是 2 + 4 只用了兩張錢，達(dá)成了我們的目標(biāo)金額。
解題思路：
同樣我們也需要?jiǎng)?chuàng)建一個(gè)數(shù)組去存儲(chǔ)當(dāng)前面額達(dá)到目標(biāo)金額所需要的張數(shù)，數(shù)組的長(zhǎng)度是 目標(biāo)金額 + 1（這其實(shí)是為了代碼的可讀性做考量）。我們將這個(gè)數(shù)組命名成nums
1. 所以現(xiàn)在我們有一個(gè)數(shù)組 nums = [ 0, 0, 0, 0, 0, 0, 0 ]，數(shù)組長(zhǎng)度為7，下標(biāo)索引對(duì)應(yīng)的是目標(biāo)金額。1代表目標(biāo)金額是1。
2. 然后我們需要開始計(jì)算當(dāng)前面額達(dá)到目標(biāo)金額所需要的張數(shù)是多少？
????首先我們需要判斷當(dāng)前面額是否小于目標(biāo)金額，因?yàn)橹挥行∮谀繕?biāo)金額我們才能拼湊出它。當(dāng)當(dāng)前面額小于目標(biāo)金額的時(shí)候我們開始計(jì)算，我們從1開始，因?yàn)檫_(dá)成0不需要任何面額。
????我們第一個(gè)面額是1，1 小于等于 1，所以我們用1 - 1 = 0，等號(hào)左邊的減數(shù)是1，因此我們需要一枚一元的錢，更新數(shù)組，[ 0, 1, 0, 0, 0, 0, 0 ]。我們接下來到目標(biāo)金額2，2 - 1 = 1，等號(hào)左右兩邊都有一個(gè)1 所以 1 + 1等于 2，因此我們需要2枚一元硬幣。接下來就以此類推了。因?yàn)? - 1 = 2，我們知道2的情況，所以 1 + 2 = 3。因此我們最終的數(shù)組如圖所示。
后面的面額也是同樣輸入進(jìn)來，然后我們做同樣的判斷，因此如圖，在不同面額的時(shí)候我們得到了不同的操作數(shù)。在這里再提一下，當(dāng)面額為2的時(shí)候，我們?cè)趺吹玫?。因?yàn)? - 2 = 3 我們知道面額為2需要一張，面額3的時(shí)候我們知道面額3的情況，因?yàn)樵诟?之前我們更新了3，所以只要用3的情況加上一張2，也就是 2 + 1 = 3，所以在面額為2時(shí)達(dá)成目標(biāo)金額5需要三張錢。
最后我們只需要在更新數(shù)組的時(shí)候和前面所需要的操作數(shù)做對(duì)比，更新最小的那個(gè)操作數(shù)就行了。因此我們可以得到偽代碼如圖
偽代碼中的 1 + nums[ 目標(biāo)金額 - 當(dāng)前面額] 中的1代表的是當(dāng)前面額的數(shù)量， 5 - 2 中的2，我們需要一張2面額的錢。
時(shí)間復(fù)雜度和空間復(fù)雜度分析：
空間復(fù)雜度時(shí) 目標(biāo)金額的大小 n，因此時(shí)O(n)
時(shí)間復(fù)雜度是，面額數(shù)組的大小d，和目標(biāo)金額的大小n，這兩個(gè)數(shù)組是個(gè)我們需要嵌套循環(huán)，所以是O(n* d)
代碼部分
