LeetCode 冥想：硬币找零

WBOY

发布时间：2024-08-19 09:11:18

987人浏览过

来源于dev.to

转载

leetcode 冥想：硬币找零

我们先来描述一下这个问题：

给你一个代表不同面额硬币的整数数组硬币和代表总金额的整数金额。返回弥补该金额所需的最少硬币数量。如果任何硬币组合都无法弥补该金额，则返回-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).

Text-To-Song

免费的实时语音转换器和调制器

下载

注意
在这个问题中，最小价值的硬币是 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];
}