Coin Change

Q: Wie hoch ist die Zeitkomplexität von Coin Change?

Die Lösung mit dynamischer Programmierung benötigt O(amount × coins) Zeit und O(amount) Speicherplatz: einen Tabelleneintrag pro Betrag, wobei für jeden Eintrag jede Münze überprüft wird. Eine einfache Rekursion ohne Memoisierung hat eine exponentielle Laufzeit in Bezug auf den Betrag.

Q: Ist Top-down oder Bottom-up besser für Coin Change?

Beide leisten dieselbe Arbeit mit O(amount × coins) . Die Top-down-Rekursion kann so tief verschachtelt sein wie der Betrag, was bei 10^4 in mehreren Sprachen zu einem Überlauf des Aufrufstapels führt. Bottom-up füllt die Tabelle mit einer Schleife, hat daher keine Tiefenbegrenzung und ist im Vorstellungsgespräch die sicherere Wahl.

MittelDynamische Programmierung

+10

Du erhältst eine Liste coins mit verschiedenen Münzwerten und einen Zielbetrag amount. Du kannst jeden Münzwert beliebig oft verwenden. Gib die kleinste Anzahl an Münzen zurück, deren Werte sich genau zu amount addieren, oder -1, wenn keine Kombination von Münzen diesen Betrag erreicht. Für einen Betrag von 0 werden 0 Münzen benötigt.

Funktion

coinChange(coins: integer-array, amount: integer) → integer

coinsinteger-array: die verschiedenen Münzwerte, die beliebig oft verwendet werden können
amountinteger: den exakt zu zahlenden Gesamtbetrag
Gibt zurückinteger: die wenigsten benötigten Münzen oder -1, wenn sich der Betrag nicht bilden lässt

Einschränkungen

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Alle Münzwerte sind unterschiedlich.

Beispiele

Eingabe: coins = [2, 5, 10]amount = 27
Ausgabe: 4
Erklärung: 10 + 10 + 5 + 2 ergibt mit vier Münzen 27. Drei Münzen reichen nicht: 27 ist ungerade, also brauchen sie genau eine 5, und die anderen beiden ergeben höchstens 20, weniger als 22.

Weiterführende Frage

Kannst du zählen, wie viele verschiedene Münzkombinationen zusammen amount ergeben, anstatt die geringste Anzahl an Münzen zu finden?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die größte passende Münze zu nehmen, schlägt fehl: Mit den Münzen 1, 3 und 4 ergibt sich für 6 die Zahlung 4 + 1 + 1, während 3 + 3 nur zwei Münzen benötigt. Die minimale Münzanzahl für einen Betrag hängt nur von der minimalen Münzanzahl für kleinere Beträge ab. Daher berechnest du jeden Betrag von 0 bis amount genau einmal.

Probiere jede Kombination mit Rekursion aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Wenn die letzte Münze, die du bezahlst, c wert ist, ergeben die Münzen davor möglichst günstig remaining - c. Also ist fewest(remaining) um eins größer als das beste fewest(remaining - c) unter allen passenden Münzen. Dabei werden alle Münzfolgen ausprobiert, die den Betrag nicht überschreiten können. Daher kann die beste Folge nicht übersehen werden.

Es löst dieselben Beträge immer wieder. Mit den Münzen 2, 5 und 10 wird der Betrag 27 nach dem Bezahlen von 10 + 2, 2 + 10, 5 + 5 + 2 und weiteren Reihenfolgen zu 15, und jedes Mal werden die 15 von Grund auf neu berechnet. Die Anzahl der Aufrufe wächst exponentiell mit dem Betrag.

Algorithmus

Schreibe eine Hilfsfunktion fewest(remaining), die die geringstmögliche Anzahl an Münzen für remaining zurückgibt oder -1, wenn keine Lösung möglich ist.
Wenn remaining 0 ist, gib 0 zurück.
Rufe für jede Münze, die nicht größer als remaining ist, die Hilfsfunktion mit dem Restbetrag nach dem Bezahlen dieser Münze auf.
Behalte das kleinste Ergebnis bei, das nicht -1 ist, und addiere eins für die bezahlte Münze.
Gib diese Anzahl zurück oder -1, wenn keine Münze zu einer Lösung geführt hat. Die Antwort ist fewest(amount).

def coinChange(coins, amount):
    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        return best

    return fewest(amount)

Rekursion mit Memoisierung

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Die Rekursion fragt nur nach Beträgen von 0 bis amount. Speichere jede Antwort in einem Array, sobald du sie zum ersten Mal berechnest, und gib den gespeicherten Wert zurück, wenn derselbe Betrag erneut vorkommt. Jeder Betrag wird einmal mit einer Schleife über die Münzen berechnet: Aufwand O(amount × coins).

Die Aufrufe werden weiterhin für jede bezahlte Münze um eine Ebene verschachtelt. Bei einer Münze im Wert von 1 sind das bis zu 10^4 Ebenen, mehr als der standardmäßige Aufrufstapel in vielen Sprachen zulässt.

Algorithmus

Erstelle ein Array memo mit Platz für jeden Betrag von 0 bis amount, das einen Marker enthält, der bedeutet, dass der Betrag noch nicht berechnet wurde.
Gib in fewest(remaining) für 0 den Wert 0 zurück und gib memo[remaining] zurück, falls dort bereits ein Ergebnis gespeichert ist.
Andernfalls probiere jede passende Münze wie bei der einfachen Rekursion aus und behalte das kleinste Ergebnis plus eins.
Speichere das Ergebnis, einschließlich -1, in memo[remaining], bevor du es zurückgibst.
Gib fewest(amount) zurück.

def coinChange(coins, amount):
    # memo[r] holds the answer for r once it is worked out; None means not yet
    memo = [None] * (amount + 1)

    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        if memo[remaining] is not None:
            return memo[remaining]
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        memo[remaining] = best
        return best

    return fewest(amount)

Bottom-up-Dynamische Programmierung über Beträge

Idee

Fülle eine Tabelle fewest von 0 aufwärts. Wenn du eine Gesamtsumme t erreichst, ist jede kleinere Summe bereits bestimmt, sodass fewest[t] um eins größer ist als das kleinste fewest[t-c] unter den passenden Münzen c.

Summen, die sich mit keiner Münzkombination erreichen lassen, enthalten den Marker amount + 1. Jede Münze ist mindestens 1 wert, daher verwendet eine echte Antwort nie mehr als amount Münzen, und der Marker verliert jeden Vergleich. Eine Schleife ersetzt die Rekursion, sodass die Tiefe des Aufrufstapels nie eine Rolle spielt.

Algorithmus

Erstelle fewest mit amount + 1 Einträgen, die alle auf den Marker amount + 1 gesetzt sind, und setze fewest[0] auf 0.
Betrachte für jede Summe t von 1 bis amount jede Münze c mit c ≤ t.
Wenn fewest[t-c] + 1 kleiner als fewest[t] ist, speichere diesen Wert in fewest[t].
Gib nach der Schleife -1 zurück, wenn fewest[amount] noch den Marker enthält, andernfalls fewest[amount].

def coinChange(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and fewest[total - coin] + 1 < fewest[total]:
                fewest[total] = fewest[total - coin] + 1
    return fewest[amount] if fewest[amount] != impossible else -1

Stolperfallen und Grenzfälle

Zuerst die größte Münze nehmen. Bei den Münzen 3 und 5 und dem Betrag 9 werden 5 und 3 genommen; bei 1 bleibt der Algorithmus stecken und gibt -1 zurück, obwohl 3 + 3 + 3 funktioniert.
Die größte ganze Zahl als Markierung verwenden. Wird 1 dazu addiert, kommt es zu einem Überlauf und die Zahl wird negativ, sodass sie dann jeden Vergleich gewinnt. Verwende amount + 1.
Zu einer Sackgasse 1 addieren. Ein Zweig, der -1 zurückgibt, ergibt zusammen mit der bezahlten Münze 0 und gewinnt jeden Vergleich. Ergebnisse von -1 überspringen.
amount Ebenen tief rekursiv aufrufen. Bei einer Münze im Wert von 1 und einem Betrag von 10^4 stoppt Python bei der standardmäßigen Grenze von 1000 Ebenen, und auch JavaScript, Dart, Ruby und R laufen über.
fewest[t-c] für eine Münze lesen, die größer als t ist, also vor dem Anfang der Tabelle.

Häufige Fragen3

Warum scheitert der Greedy-Ansatz beim Münzwechselproblem?

Die größte passende Münze zu nehmen, ist nur bei manchen Münzsystemen sicher, etwa bei den meisten realen Währungen. Mit den Münzen 1, 3 und 4 lässt sich 6 mit drei Münzen statt mit zwei bezahlen, und mit den Münzen 3 und 5 lässt sich 9 überhaupt nicht bezahlen. Dynamische Programmierung vergleicht alle Möglichkeiten, sodass kein Münzsystem sie täuscht.

Wie hoch ist die Zeitkomplexität von Coin Change?

Die Lösung mit dynamischer Programmierung benötigt O(amount × coins) Zeit und O(amount) Speicherplatz: einen Tabelleneintrag pro Betrag, wobei für jeden Eintrag jede Münze überprüft wird. Eine einfache Rekursion ohne Memoisierung hat eine exponentielle Laufzeit in Bezug auf den Betrag.

Ist Top-down oder Bottom-up besser für Coin Change?

Beide leisten dieselbe Arbeit mit O(amount × coins). Die Top-down-Rekursion kann so tief verschachtelt sein wie der Betrag, was bei 10^4 in mehreren Sprachen zu einem Überlauf des Aufrufstapels führt. Bottom-up füllt die Tabelle mit einer Schleife, hat daher keine Tiefenbegrenzung und ist im Vorstellungsgespräch die sicherere Wahl.

def coinChange(coins, amount):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

coins = [2, 5, 10]
amount = 27

Erwartete Ausgabe

Coin Change

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Kombination mit Rekursion aus

Rekursion mit Memoisierung

Bottom-up-Dynamische Programmierung über Beträge

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben