解法1：
在暴力的基础上利用空间记录已求过的值达到剪枝的目的
class Solution
{
public:int coinChange(vector<int> &coins, int amount){
vector<int> memo(amount + 1, -2);return helper(coins, amount, memo);}int helper(vector<int> &coins, int amount, vector<int> &memo){
if (amount == 0)return 0;if (memo[amount] != -2)return memo[amount];int minTimes = INT_MAX;for (int coin : coins){
if (coin > amount)continue;int subTims = helper(coins, amount - coin, memo);if (subTims == -1)continue;minTimes = min(minTimes, subTims + 1);}memo[amount] = minTimes == INT_MAX ? -1 : minTimes;return memo[amount];}
};
解法2：
dp 自下而上的思考
class Solution
{
public:int coinChange(vector<int> &coins, int amount){
vector<int> dp(amount + 1, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; i++)for (int coin : coins){
if (coin <= i)dp[i] = min(dp[i], dp[i - coin] + 1);}return dp[amount] > amount ? -1 : dp[amount];}
};