一、题目
二、思路
(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];//返回需要的硬币数 } };