題目描述
如果我們有面值1元访诱，3元和5元的硬幣若干图张，如何用最少的硬幣湊夠11元锋拖？
- 如何用最少的硬幣湊夠i元？
當 i = 0 時祸轮，顯然需要0個硬幣兽埃。
這里我們使用 d(i) = j 來描述，于是我們有 d(0) = 0适袜。
當 i = 1 時柄错，只有1元硬幣可用，當我使用1個1元硬幣苦酱，在去求解如果 i = 0這個問題售貌，前面已經(jīng)球得這個問題的解為0，所以i=1時這個問題求解結束疫萤，得到取1個1元硬幣這個解趁矾，所以d(1) = 1。
當 i = 2 時给僵， 可以使用2個1元硬幣，這個過程首先，取1個1元硬幣帝际，然后去求解i=1這個問題蔓同，上面已經(jīng)有了這個問題的解答，所以這個問題求解結束蹲诀，這種情況需要2個1元硬幣斑粱。還有一種情況去一個2元硬幣，然后去求解i = 0這個問題脯爪，上面也已經(jīng)有了解答则北，所以這種情況下，需要1個2元硬幣痕慢。因為問題是要求硬幣數(shù)最少尚揣，所以去上面兩種情況中，結果較小的1個作為結果掖举，即min{1+d(1),1+d(0)},所以結果為d(2) = 1快骗。
當 i = 3 時，我們用按照上述方式求解塔次，過程的公式化為1) d(3) = min{1+d(3-1),1+d(3-3)} = min{1+d(2),1+d(1),1+d(0)} = min{2,2,1} = 1
由以上的的過程我們可以得到兩個非常重要的概念方篮，狀態(tài)和狀態(tài)轉(zhuǎn)移方程。上文中d(i)表示湊夠i元需要的最少硬幣數(shù)励负，我們將它定義為狀態(tài)藕溅。我們根據(jù)子問題來找到狀態(tài)的描述。最終我們求解的問題继榆，可以用這個狀態(tài)來表示巾表，即d(11)。那什么是狀態(tài)轉(zhuǎn)移方程呢裕照？,既然我們用d(i)表示狀態(tài)攒发，那么狀態(tài)轉(zhuǎn)移方程自然包含d(i)，上文中包含d(i)的方程是d(3) = min{1+d(3-1),1+d(3-3)}晋南，沒錯惠猿，他就是狀態(tài)轉(zhuǎn)移方程，描述狀態(tài)之間是如何轉(zhuǎn)移的负间。這里我們對它一般化d(i) = min{d(i-vj)+1} 其中i-vj >=0偶妖，vj表示第j個硬幣的面值。 j = 1,2,3 vj = 1 , 3, 5政溃。
下面是解題的代碼
vector<int> coins{1,3,5};
int coinChange(vector<int>& coins, int amount) {
vector<int> dp;
for (int i=0;i<=amount;i++) {
dp.push_back(9999);
}
dp[0] =0;
for (int i = 1;i<=amount;i++)
for (int j = 0;j < coins.size();j++)
if ((i-coins[j] >= 0)&&(dp[i]>dp[i-coins[j]]+1))
dp[i] = dp[i-coins[j]]+1;
if (dp[amount] == 9999)
return -1;
else
return dp[amount];
}
