一、题目
二、思路
（1）确定状态
d p [ n ] dp[n]dp[n]表示拼成n元最少需要的硬币数。
（2）状态转移方程
本题在dp入门中有讲，确定状态转移方程，如：若只有2元、5元、7元，现要拼成x元，状态转移方程就是f ( x ) = m i n ( f ( x − 2 ) , f ( x − 5 ) , f ( x − 7 ) ) + 1 f(x)=min ( f(x-2),f(x-5),f(x-7) )+1f(x)=min(f(x−2),f(x−5),f(x−7))+1，而本题是任何整数额的硬币都有，就for遍历就好啦。
（3）边界条件+初始情况
f[0]=0，f[i]=maxn。
（4）计算顺序
注意
（1）内层for循环的if判断（i-coins[j]可能是负数，即如果有3块钱则最后一枚硬币不阔能是5块钱）；
（2）if的第二个判断为f[i-coins[j]]!=maxn，即如果要拼27元，最后一枚硬币是5块钱，即求“最少用多少枚硬币拼成22块钱，然后这个硬币数+1即可”，但是有可能拼不出22块——即为无穷大的情况。
内层的for循环的最后一枚硬币表示前i枚硬币（即1、2、…i）取出多少没硬币可以拼成amount。
三、代码
class Solution { public: int coinChange(vector<int>& coins, int amount) { int maxn=0x07ffffff;//无穷大 //coins.resize(amount+1); int n=coins.size();//硬币的个数 vector<int>f; f=coins; f.resize(amount+1); //初始化 f[0]=0; //f[1],f[2],...,f[27] int i,j; //f[1],f[2],...f[27] for(i=1;i<=amount;i++){ f[i]=maxn;//初始化为无穷大 //最后一枚硬币，即前i枚硬币。 //f[i]=min{f[i-A[0]]+1,...,f[i-A[n-1]]+1} for(j=0;j<n;j++){ if(i>=coins[j]&&f[i-coins[j]]!=maxn){ f[i]=min(f[i-coins[j]]+1,f[i]); } } } if(f[amount]==maxn){ f[amount]=-1; } return f[amount];//返回需要的硬币数 } };
