5. 零钱兑换（LeetCode-322）
题目
给你一个整数数组 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] <= 231 - 1
0 <= amount <= 104
思路
五部曲
dp[j] 含义
凑成总金额为 j jj 所需的最少硬币数
递推公式
求最少硬币数，一种就是不含当前物品（这里说的当前物品就是指当前的这枚硬币，假如当前硬币值为2，不是说背包里就不含硬币值为2的硬币了，因为是硬币无限枚，所以很可能有，而是说不含当前这枚硬币值为2的硬币）的硬币数，数值保持不变。另一种是含当前物品的硬币数，数值要加一（加上当前物品）
d p [ j ] = m i n ( d p [ j ] , d p [ j − c o i n s [ i ] ] + 1 )
数组初始化
凑成总金额为2的硬币数肯定为零，而其他要初始化为最大值，不然在运行递推公式时初始值会覆盖 d p [ j − c o i n s [ i ] ] + 1
遍历顺序
都行
代码实现
class Solution { public: int coinChange(vector<int> &coins, int amount) { 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++) { // 如果dp[j - coins[i]]是初始值则跳过 if (dp[j - coins[i]] != INT_MAX) { dp[j] = min(dp[j], dp[j - coins[i]] + 1); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; } };
易错点在 d p [ j − c o i n s [ i ] ] dp[j - coins[i]]dp[j−coins[i]] 是初始值没有跳过，还有记得没有任何一种硬币组合能组成总金额，返回 -1
