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中文網其他相關文章！