ENDEAR
Kostenlos starten
Algorithmuspro

Dynamische Programmierung: Münzwechsel

Finde die wenigsten Münzen für einen Betrag, ein Problem, bei dem es schiefgeht, immer die größte Münze zu nehmen.

Zeit
O(n·m)
Speicher
O(n)

// Schritt für Schritt

Schritt 1 / 15
1function coinChange(coins, amount) {2  const dp = new Array(amount + 1).fill(Infinity);3  dp[0] = 0;4  for (let a = 1; a <= amount; a++) {5    for (const c of coins) {6      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;7    }8  }9  return dp[amount] === Infinity ? -1 : dp[amount];10}
coins
= [1, 3, 4]
  1. 00
  2. ∞1
  3. ∞2
  4. ∞3
  5. ∞4
  6. ∞5
  7. ∞6

dp[0] = 0: Null Münzen ergeben 0. Jeder andere Betrag startet bei ∞, also noch nicht erreichbar.

// pro-lektion

Den ganzen Durchlauf freischalten

Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.

Preise ansehen

So funktioniert es

Mit den Münzen 1, 3 und 4 wählt der gierige Ansatz für 6 die Kombination 4 + 1 + 1, dabei reichen mit 3 + 3 zwei Münzen. Dynamische Programmierung probiert jede Möglichkeit, ohne Arbeit zu wiederholen: dp[a] ist die kleinste Münzanzahl für den Betrag a, und für jede Münze c ist dp[a − c] + 1 ein Kandidat. Fülle dp von 0 bis zum Betrag. O(n·m) Zeit für den Betrag n und m Münzen, und O(n) Speicher.

Dieses Muster erkennen üben →