来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1：
- 输入：coins = [1, 2, 5], amount = 11
- 输出：3
- 解释：11 = 5 + 5 + 1
示例 2：
- 输入：coins = [2], amount = 3
- 输出：-1
说明:
你可以认为每种硬币的数量是无限的。
二、题解
以示例一种的[1, 2, 5]三种硬币为例，当要凑到11块钱的时候，什么时候硬币个数最小？
只有在凑到11之前的硬币最少，凑够11的硬币才最少。凑到11块一种有三种可能性：
- 已经有10块了，再凑1块得到11块。
- 已经有9块了，再凑2块得到11块。
- 已经有6块了，再凑5块得到11块。
也就是说，手里面当前已经揣了10块、9块或是6块钱，这个时候哪个的硬币数量最少，凑成的11块钱硬币才最少。很明显又是一个动态规划，以dp[i]表示amount=i时候的最优解个数，那么dp[i]的状态转移方程为：
$$\begin{equation} dp(i)= \begin{cases} -1 & amount < 0\\ 0 & amount = 0 \\ min(dp[i-coin1], dp[i-coin2], ...) + 1 & amount > 0\end{cases} \end{equation}$$
三、代码
class Solution {
public:
int coinChange(vector<int> &coins, int amount) {
int i, cnt;
// 初始化为int类型的最大值以方便做特殊处理
vector<int> dp(amount + 1, INT_MAX);
if (amount < 0)
return -1;
dp[0] = 0;
for (i = 1; i <= amount; i++) {
for (auto coin: coins) {
// dp[i - coin]存在并且有最小值才行
if (i - coin < 0 || dp[i - coin] == INT_MAX)
continue;
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
