LeetCode-Meditationen: Münzwechsel

Beginnen wir mit der Beschreibung dieses Problems:

Sie erhalten eine ganzzahlige Array-Münze, die Münzen verschiedener Nennwerte darstellt, und einen ganzzahligen Betrag, der einen Gesamtgeldbetrag darstellt.

Geben Sie so wenig Münzen zurück, wie Sie für diesen Betrag benötigen. Wenn dieser Geldbetrag durch keine Kombination der Münzen gedeckt werden kann, geben Sie -1 zurück.

Sie können davon ausgehen, dass Sie von jeder Münzart unendlich viele haben.

Zum Beispiel:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Oder:

Input: coins = [2], amount = 3
Output: -1

Oder:

Input: coins = [1], amount = 0
Output: 0

Außerdem gibt eine unserer Einschränkungen an, dass 1 <= Münzen.Länge <= 12.

---

Dieses Problem ist tatsächlich bekannt und Sie haben es vielleicht im Zusammenhang mit einem Gierproblem gesehen. Allerdings erfordert diese Version, dass wir die geringste Anzahl Münzen finden, und ein gieriger Ansatz würde nicht funktionieren.
Warum das so ist, wird in einem NeetCode-Video anschaulich gezeigt: Wenn unsere Münzen beispielsweise [1, 3, 4, 5] sind und der Betrag 7 beträgt, erhält der gierige Ansatz zuerst 5 und versucht dann alle maximale Beträge, bis es sich mit zwei Einsen begnügen muss, sodass die Summe 5, 1 und 1 ergibt. Wir können jedoch auch weniger Münzen verwenden: 4 und 3. Schauen wir uns also an, wie wir vorgehen könnten das tun.

Wir müssen den Betrag irgendwie aufbauen, um die Mindestanzahl an Münzen zu erreichen, die wir verwenden können. Beginnen wir dazu mit der Initialisierung eines Arrays:

let dp = Array.from({ length: amount + 1 }, () => amount + 1);




</p>
<p>Wir haben dieses Array mit der Länge Betrag + 1, da <mark>jeder Index die Mindestanzahl an Münzen enthält, die wir für jeden Betrag verwenden können.</mark>Zum Beispiel enthält Index 0 unseres dp-Arrays den Wert von Mindestanzahl an Münzen, die wir für den Betrag 0 verwenden können; In ähnlicher Weise enthält Index 7 den Wert der Mindestanzahl an Münzen, die wir für den Betrag von 7 verwenden können.</p>

<p>Wir initialisieren jeden Index mit dem Platzhalterwert Betrag + 1, da die maximale Anzahl an Münzen den Betrag nicht überschreiten kann (beispielsweise beträgt die maximale Anzahl an Münzen, die wir für 7 verwenden können, 7: 1 + 1 + 1 +). 1 + 1 + 1 + 1).</p>

<div class="table-wrapper-paragraph"><table>
<thead>
<tr>
<th>Note</th>
</tr>
</thead>
<tbody>
<tr>
<td>The minimum valued coin is 1 in this problem, as one of the constraints indicates.</td>
</tr>
</tbody>
</table></div>

<p>Für den Betrag 0 ist die Mindestanzahl an Münzen, die wir verwenden können, offensichtlich: 0:<br>
</p>

<pre class="brush:php;toolbar:false">dp[0] = 0;

Dann durchlaufen wir dieses Array, beginnend mit Index 1, und durchlaufen für jeden Index die Münzen:

for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) {
  for (const coin of coins) {
    /* ... */
  }
}

Wenn die Münze, die wir betrachten, für diesen Betrag verwendet werden kann (d. h. amountIdx - Münze >= 0), dann aktualisieren wir den Wert für diesen Betrag in unserem dp-Array. Es wird entweder das Minimum des Wertes sein, den wir bereits haben, oder 1 + dp[amountIdx - Münze]:

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.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Münzwechsel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!