Treppensteigen und Münzkombinationen
Klassische eindimensionale Rekurrenzen von Grund auf
Treppensteigen und Münzkombinationen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Treppensteigen kennenlernen
Sie können jeweils 1 oder 2 Stufen auf einmal gehen. Wie viele Möglichkeiten gibt es, die Stufe n zu erreichen? Diese klassische 1D-DP ist eigentlich nur Fibonacci in Verkleidung.
Die Rekurrenz finden
Um auf Stufe i zu stehen, kamen Sie von i-1 oder i-2. Daher gilt dp[i] = dp[i-1] + dp[i-2], wobei die beiden letzten Schritte addiert werden.
dp[i] = dp[i-1] + dp[i-2]Die Basisfälle festlegen
Es gibt eine Möglichkeit, am Boden zu bleiben, und eine Möglichkeit, Stufe 1 zu erreichen. Diese Basisfälle bilden den Ausgangspunkt für die gesamte Tabelle.
dp[0], dp[1] = 1, 1Füllen und Ergebnis ablesen
Gehen Sie die Tabelle aufsteigend durch; dann enthält die letzte Zelle die Anzahl. Die vollständige Lösung ist eine kleine Tabellierungs-Schleife.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Auf zwei Variablen reduzieren
Sie benötigen nur die letzten beiden Werte und können daher das Array weglassen. Diese Variante mit O(1)-Speicher ist bei Wettbewerben besonders beliebt.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bZu Münzkombinationen wechseln
Gegeben sind Münzwerte; zählen Sie, auf wie viele Arten sich der Betrag A bilden lässt. Die Reihenfolge spielt hier keine Rolle, daher zählen wir Kombinationen statt Folgen.
coins = [1, 2, 5]Die Kombinationstabelle
Sei dp[x] die Anzahl der Möglichkeiten, x zu bilden. Beginnen Sie mit einer Möglichkeit, null zu bilden: der leeren Menge von Münzen.
dp = [0]*(A+1)
dp[0] = 1Die Münzschleife außen platzieren
Platzieren Sie die Münzschleife außen um die Betragsschleife. Diese Reihenfolge zählt jede Kombination genau einmal und niemals mehrere Permutationen.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Kombinationen und Permutationen
Wenn Sie die Schleifenreihenfolge vertauschen, zählen Sie stattdessen geordnete Möglichkeiten. Allein die Verschachtelung der Schleifen verändert die Bedeutung des Ergebnisses.
Variante: Minimale Münzanzahl
Für die kleinste Münzanzahl speichern Sie statt einer Summe ein Minimum. Initialisieren Sie mit unendlich und addieren Sie 1 zum besten Teilproblem.
dp[x] = min(dp[x], dp[x-c] + 1)Ein Muster, viele Ausprägungen
Treppen und Münzen haben dieselbe Struktur: Jeder Zustand bildet eine Summe oder ein Minimum über einige vorherige Zustände. Wenn Sie das erkennen, schreibt sich der Code fast von selbst.
Schnelltest
Welche Schleifenreihenfolge vermeidet beim Zählen von Münzkombinationen Duplikate?
Zusammenfassung: Die letzten Schritte addieren
Sie können jetzt Treppensteigen und Münzzählen mit einer 1D-Rekurrenz lösen. Jedes Ergebnis addiert einige frühere Zustände, und die Schleifenreihenfolge entscheidet zwischen Kombinationen und Permutationen.
Häufig gestellte Fragen
Ist die Lektion „Treppensteigen und Münzkombinationen“ kostenlos?
Ja — der vollständige Text von „Treppensteigen und Münzkombinationen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Treppensteigen und Münzkombinationen“?
Klassische eindimensionale Rekurrenzen von Grund auf Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Treppensteigen und Münzkombinationen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Memoization oder Tabulation
- Zustand und Übergang definieren
- Treppensteigen und Münzkombinationen
- Längste aufsteigende Teilfolge