题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
解题方法
动态规划
本题在 518. 零钱兑换 II 的基础上求组成amount的最小硬币数，为完全背包问题。设定动态数组dp[j]表示凑齐j需要的最小硬币数，则有如下递推关系：

初始化条件为dp[0] = 0，应为递推过程中需要求解最小值，所以其余值初始化为INT_MAX
C++代码：
```
class Solution {
public:
  int coinChange(vector<int>& coins, int amount) {
      if(!amount) return 0;
      vector<int> dp(amount+1, INT_MAX);
      dp[0] = 0;
      for(int i=0; i<coins.size(); i++) {
          for(int j=coins[i]; j<=amount; j++) {
              if(dp[j-coins[i]]==INT_MAX) continue;
              dp[j] = min(dp[j], dp[j-coins[i]]+1);  
          }
      }
      return (dp[amount] == INT_MAX ? -1 : dp[amount]);
  }
};
```
贪心+记忆搜索
通过贪心算法遍历所有可能，途中记录不同总金额对应的最小硬币数。
C++代码： ```cpp class Solution { private: vectorcount;

public: int dfs(vector& coins, int amount) { if(amount<0) return -1; if(amount==0) return 0; if(count[amount-1] != 0) return count[amount-1]; int tmp = INT_MAX; for(int i=0; i=0 && res<tmp) tmp = res+1; } count[amount-1] = (tmp == INT_MAX ? -1 : tmp); return count[amount-1]; }

int coinChange(vector<int>& coins, int amount) {
    if (amount < 1) return 0;
    count.resize(amount);
    return dfs(coins, amount);
}

}; ```

LeetCode

322. 零钱兑换

题目

解题方法

动态规划

贪心+记忆搜索