题目
给你一个整数数组 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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
解答
- 动态规划
解题思路：
- 创建一个长度为 amount + 1 的数组
dp，用于保存每个金额对应的最小硬币数量。初始时，将数组中所有元素的值设置为一个较大的值，表示无穷大。 - 将金额为 0 的最小硬币数量设为 0。
- 通过动态规划的方式，遍历每个金额，计算最小硬币数量。
- 对于当前金额 i，遍历每个硬币的面值，如果当前硬币面值小于等于当前金额 i，则计算使用当前硬币后的剩余金额 remainder。
- 检查剩余金额的最小硬币数量是否为有效值，如果是，则更新当前金额 i 的最小硬币数量为
dp[remainder] + 1（加 1 表示使用了当前硬币）。 - 最终，如果最终金额的最小硬币数量仍为无效值（即未被更新），则返回 -1，否则返回最小硬币数量。
#include <vector>
#include <climits>
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 创建一个长度为 amount + 1 的数组，用于保存每个金额对应的最小硬币数量
vector<int> dp(amount + 1, INT_MAX);
// 初始化金额为 0 的最小硬币数量为 0
dp[0] = 0;
// 遍历每个金额，计算最小硬币数量
for (int i = 1; i <= amount; ++i) {
// 遍历每个硬币的面值
for (int j = 0; j < coins.size(); ++j) {
// 如果当前硬币面值小于等于当前金额 i
if (coins[j] <= i) {
// 计算使用当前硬币后的剩余金额
int remainder = i - coins[j];
// 检查剩余金额的最小硬币数量是否为有效值
if (dp[remainder] != INT_MAX) {
// 更新当前金额 i 的最小硬币数量
dp[i] = min(dp[i], dp[remainder] + 1);
}
}
}
}
// 如果最终金额的最小硬币数量为无效值，则返回 -1，否则返回最小硬币数量
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};- 动态规划（优化）
- 通过使用范围-based for 循环遍历硬币面值，可以简化代码并提高可读性。
- 内层循环从硬币面值开始，而不是从 1 开始，这样可以避免重复计算和无效的更新。
- 这种优化利用了动态规划的特性，逐步计算每个金额的最小硬币数量。
#include <vector>
#include <climits>
#include <algorithm>
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 创建一个长度为 amount + 1 的数组，用于保存每个金额对应的最小硬币数量
vector<int> dp(amount + 1, amount + 1);
// 初始化金额为 0 的最小硬币数量为 0
dp[0] = 0;
// 动态规划，遍历每个金额，计算最小硬币数量
for (int coin : coins) {
for (int i = coin; i <= amount; ++i) {
// 更新当前金额 i 的最小硬币数量
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
// 如果最终金额的最小硬币数量仍然大于 amount，则表示无法凑出该金额，返回 -1
if (dp[amount] > amount) {
return -1;
} else {
// 返回最小硬币数量
return dp[amount];
}
}
};