我们先来描述一下这个问题：
给你一个代表不同面额硬币的整数数组硬币和代表总金额的整数金额。 返回弥补该金额所需的最少硬币数量。如果任何硬币组合都无法弥补该金额，则返回-1。 您可以假设您拥有无限数量的每种硬币。
例如：
input: coins = [1, 2, 5], amount = 11 output: 3 explanation: 11 = 5 + 5 + 1
或者：
input: coins = [2], amount = 3 output: -1
或者：
input: coins = [1], amount = 0 output: 0
此外，我们的约束之一表明 1
这个问题实际上是一个熟悉的问题，您可能在贪婪问题的背景下见过它。然而，这个版本要求我们找到最少数量的硬币，贪心的方法是行不通的。
neetcode 视频清楚地展示了为什么会这样：例如，如果我们的硬币是 [1, 3, 4, 5] 并且数量是 7，贪婪方法将首先得到 5，然后它会尝试所有 最大 数量，直到它必须满足两个 1，使其总数为 5、1 和 1。但是，我们可以使用比这更少的硬币：4 和 3。所以，让我们看看如何做到这一点。
我们必须以某种方式积累到我们可以使用的最小硬币数量。为此，我们从初始化一个数组开始：
let dp = array.from({ length: amount + 1 }, () => amount + 1);
我们有这个长度为 amount + 1 的数组，因为每个索引将保存每个金额可以使用的最小硬币数量。例如，dp 数组的索引 0 将保存我们可以使用的最小硬币数量的值使用量为0；同样，索引 7 将保存我们可以使用 7 的最小硬币数量的值。
我们用amount + 1的占位符值初始化每个索引，因为最大硬币数量不能超过amount（例如，我们可以使用7的最大硬币数量是7：1 + 1 + 1 + 1 + 1 + 1 + 1).
| 注意 |
|---|
| 在这个问题中，最小价值的硬币是 1，正如约束之一所示。 |
对于0的数量，我们可以使用的最小硬币数量是显而易见的：0：
dp[0] = 0;
然后，我们将从索引 1 开始循环遍历这个数组，对于每个索引，我们将迭代硬币：
for (let amountidx = 1; amountidx < dp.length; amountidx++) {
for (const coin of coins) {
/* ... */
}
}
如果我们正在查看的硬币可以用于该金额（即 amountidx - coin >= 0），那么我们将更新 dp 数组中该金额的值。它将是我们已经拥有的值的最小值，或者 1 + dp[amountidx - coin]:
for (let amountidx = 1; amountidx < dp.length; amountidx++) {
for (const coin of coins) {
if (amountidx - coin >= 0) {
dp[amountidx] = math.min(dp[amountidx], 1 + dp[amountidx - coin]);
}
}
}
| 注意 |
|---|
| 1 + dp[amountidx - coin] 的原因是我们使用已经计算出的值的解，重用子问题。所以，1 是我们目前正在考虑的硬币。 |
如果最后我们无法将总金额与任何硬币组合匹配，我们必须返回-1。
检查的方法是检查最后一个元素等于 amount + 1 的条件。在这种情况下，我们可以返回 -1。否则，我们将只返回包含构成金额的最小硬币数量的最后一个元素：
function coinchange(coins: number[], amount: number): number {
/* ... */
if (dp[dp.length - 1] === amount + 1) {
return -1;
}
return dp[dp.length - 1];
}
而且，这是最终的解决方案：
function coinChange(coins: number[], amount: number): number {
let dp = Array.from({ length: amount + 1 }, () => amount + 1);
dp[0] = 0;
for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) {
for (const coin of coins) {
if (amountIdx - coin >= 0) {
dp[amountIdx] = Math.min(dp[amountIdx], 1 + dp[amountIdx - coin]);
}
}
}
if (dp[dp.length - 1] === amount + 1) {
return -1;
}
return dp[dp.length - 1];
}
时间和空间复杂度
时间复杂度为o(n*m) 在哪里 n 是金额 + 1 并且 m 是我们拥有的硬币数量。我们迭代每个值直到 amount + 1，并且对于每个值，再次迭代每个硬币，执行恒定操作。
空间复杂度取决于我们给出的数量，因为 dp 数组的大小会随着数量的增加而增长，所以我们可以说它是 o(n) 在哪里 n 是金额。
是时候深呼吸了。尽管我们通常会接受动态规划问题的解决方案，但一开始就很难得到它们——不仅要提出解决方案，还要理解已经存在的解决方案。
接下来，我们来看看最大乘积子数组问题。在那之前，祝您编码愉快。
