首先尝试暴力破解方法(暴力破解加记忆化，减少重复计算，否则会超时)：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount < 1) return 0;
count.resize(amount);
return helper(coins,amount);
}
private:
vector<int> count;
int helper(vector<int>& coins,int amount)
{
if(amount < 0) return -1;
if(amount == 0) return 0;
if(count[amount - 1] != 0) return count[amount - 1];
int ans = INT_MAX;
for(int i = 0;i < coins.size();i++)
{
int res = helper(coins,amount - coins[i]);
if(res >= 0 && res < ans)
ans = res + 1;
}
count[amount - 1] = ans == INT_MAX ? -1 : ans;
return count[amount - 1];
}
};
找零钱问题在使用动态规划DP算法时可以当成爬楼梯问题，例如我要兑换面值为1000，零钱有10，20，50 ，100，那么类比成爬楼梯为，如果要爬到1000阶楼梯，一步能走10，20，50，100（邮电脱离实际)，那么走到第1000阶最小步数，就是最后一步走10 ，20，50，100步时前面所走的最小步数（上面代码内层循环）。
最后的返回值判断是否找到兑换零钱方案，如果没有兑换方案，则保持默认值amount + 1,当然这种方法存在缺陷，当amount为INT_MAX时存在溢出，之所以没有报错是因为题目有限制amount最大值为10000.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1,Max);
dp[0] = 0;
for(int i = 1;i <= amount;i++)
{
for(int j = 0;j < coins.size();j++)
{
if(coins[j] <= i)
dp[i] = min(dp[i],dp[i - coins[j]] + 1);
}
}
return dp[amount] > amount ? -1:dp[amount];
}
};