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).

Note

The minimum valued coin is 1 in this problem, as one of the constraints indicates.

对于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]);
    }
  }
}

Note

The reason for 1 + dp[amountIdx - coin] is that we use the solution to an already calculated value, reusing the subproblem. So, 1 is the coin we're currently considering.

If, at the end, we can't match the total amount with any combination of coins, we have to return -1.
The way to check for that is to check the condition where the last element equals amount + 1. In that case, we can return -1. Otherwise, we'll just return the last element which holds the minimum number of coins that make up the amount:

function coinChange(coins: number[], amount: number): number {
  /* ... */

  if (dp[dp.length - 1] === amount + 1) {
    return -1;
  }

  return dp[dp.length - 1];
}

And, here is the final solution:

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];
}

Time and space complexity

The time complexity is $O(n\ast m)$O(n∗m) where $n$n is the amount + 1 and $m$m is the number of coins we have. We iterate through each value up to amount + 1, and for each of those values, iterate again through each coin, doing a constant operation.

The space complexity depends on the amount we're given as the size of our dp array will grow as the amount increases, so we can say that it's $O(n)$O(n) where $n$n is the amount.

---

It's time for a deep breath. Even though we usually make peace with the solutions to dynamic programming problems, it's tough getting them in the first place — not only coming up with the solutions, but also understanding the already existing ones.

Next, we'll take a look at the problem Maximum Product Subarray. Until then, happy coding.

以上是LeetCode 冥想：硬币找零的详细内容。更多信息请关注PHP中文网其他相关文章！