Dynamische Programmierung

Dynamische Programmierung (englisch: Dynamic programming, abgekürzt DP) ist eine Methode, die in Mathematik, Managementwissenschaft, Informatik, Wirtschaftswissenschaften und Bioinformatik verwendet wird und komplexe Probleme löst, indem sie das ursprüngliche Problem in relativ einfache Teilprobleme zerlegt.

Stellen Sie sich vor, Sie steigen einenTreppe mit n Stufen. Jedes Mal können Sie1eine Stufe oder2Stufen.

Also, wie viele verschiedene Möglichkeiten gibt es, bis zur Spitze des Gebäudes zu steigen?

Wenn Sie vom obersten Ziel (dernn-ten Stufe) ausgehen, mag es kompliziert erscheinen.

Aber wenn wir unsere Perspektive ändern:Um dienn. Um Stufe n zu erreichen, können Sie nurn-1einen Schritt nach oben von Stufe n-1 aus gehen, oder von dern-2Ebene, indem man zwei Stufen nach oben steigt.. Um also dienDie Anzahl der Möglichkeiten, Stufe n zu erreichen, ist gleich der Anzahl der Möglichkeiten, Stufen-1n-1 plus die Anzahl der Möglichkeiten, Stufen-2Ebene, die Anzahl der Möglichkeiten.

Diese Art vonZerlegen Sie ein großes Problem in mehrere überlappende Teilprobleme und vermeiden Sie wiederholte Berechnungen, indem Sie die Lösungen der Teilprobleme speichern, wodurch das ursprüngliche Problem effizient gelöst wird.Die Methode ist die Dynamische Programmierung (kurz DP).

Kernidee

Der Kern der dynamischen Programmierung istdas Merken der bereits berechneten Lösungen. 。

Dynamische Programmierung wird üblicherweise verwendet, um Probleme mit den folgenden Eigenschaften zu lösen:

  1. überlappende Teilprobleme: Während des rekursiven Lösungsprozesses kann dasselbe Teilproblem mehrfach berechnet werden.
  2. Optimale Substruktur: Die optimale Lösung eines Problems enthält die optimalen Lösungen seiner Teilprobleme.

Wir können ein einfaches Flussdiagramm verwenden, um den Lösungsansatz der dynamischen Programmierung zu verstehen:

Die obige Abbildung zeigt die typischen Schritte zum Lösen eines Problems der dynamischen Programmierung: Beginnen Sie mit der Definition des Problems, finden Sie durch Analyse die Teilproblemstruktur, formalisieren Sie diese dann mit Zuständen und Zustandsübergangsgleichungen, und erhalten Sie schließlich die Antwort durch klare Anfangsbedingungen und Berechnungsreihenfolge.

Von der Rekursion zur dynamischen Programmierung: das Treppensteigproblem

Lass uns das klassische"Climbing Stairs"-Problem verwenden, um den Optimierungsprozess von der Rekursion zur dynamischen Programmierung nachzuvollziehen.

Problembeschreibung

Angenommen, du steigst Treppen. Du benötigstnStufen, bevor du oben ankommst. Jedes Mal kannst du1oder2Stufen steigen. Auf wie viele verschiedene Arten kannst du nach oben steigen?

Methode 1: Brute-Force-Rekursion (ineffizient)

Basierend auf der Analyse am Anfang können wir direkt die rekursive Formel schreiben:f(n) = f(n-1) + f(n-2)wobei,f(1) = 1, f(2) = 2。

Beispiel

def climb_stairs_recursive(n: int) -> int:
    """Rekursive Lösung"""
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# Test
print(f"Anzahl der Möglichkeiten, zur 5. Stufe zu steigen (Rekursion): {climb_stairs_recursive(5)}")  # Ausgabe: 8

Analyse der Nachteile: Diese Rekursion beinhaltet eine große Menge wiederholter Berechnungen. Zum Beispiel die Berechnung vonf(5)erfordertf(4)undf(3), Berechnungf(4)erfordert wiederumf(3)undf(2), hierf(3)Es wird zweimal berechnet. Wennnn ist groß, die Zeitkomplexität ist exponentiell.O(2^n), was äußerst ineffizient ist.

Methode 2: Rekursion mit Memoisierung (Top-down)

Wir können ein Array (ein "Memo") verwenden, um bereits berechnete Ergebnisse zu speichern und wiederholte Berechnungen zu vermeiden.

Beispiel

def climb_stairs_memo(n: int) -> int:
    """Rekursion mit Memoisierung (Top-down)"""
    # Initialisiere die Memoisierungstabelle; -1 bedeutet nicht berechnet
    memo = [-1] * (n + 1)
   
    def helper(x: int) -> int:
        # Basisfall
        if x == 1:
            return 1
        if x == 2:
            return 2
        # Falls bereits berechnet, Ergebnis direkt zurückgeben
        if memo[x] != -1:
            return memo[x]
        # Andernfalls berechne es und speichere es in der Memoisierungstabelle
        memo[x] = helper(x - 1) + helper(x - 2)
        return memo[x]
   
    return helper(n)

print(f"Anzahl der Möglichkeiten, zur 5. Stufe zu gelangen (Memoisierung): {climb_stairs_memo(5)}")  # Ausgabe: 8

Die Zeitkomplexität dieser Methode reduziert sich aufO(n), da jedes Teilproblem nur einmal berechnet wird. Die Speicherkomplexität istO(n). Dies ist bereits ein Ansatz der dynamischen Programmierung, genannt"Top-Down"oder"memoisierte Suche"。

Methode 3: Iteratives Array (Bottom-up, Standard-DP)

Wir starten direkt beim kleinsten Teilproblem und arbeiten uns Schritt für Schritt zum ursprünglichen Problem vor. Üblicherweise wird ein Array verwendetdpum Zustände zu speichern.

Beispiel

def climb_stairs_dp(n: int) -> int:
    """Dynamische Programmierung (Bottom-up)"""
    if n <= 2:
        return n
    # 1. Definiere das Zustandsarray: dp[i] repräsentiert die Anzahl der Möglichkeiten, zur i-ten Stufe zu gelangen
    dp = [0] * (n + 1)
    # 2. Bestimme die Anfangsbedingungen
    dp[1] = 1
    dp[2] = 2
    # 3. Zustandsübergang: leite rekursiv gemäß der Zustandsübergangsgleichung ab
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    # 4. Gib das Endergebnis zurück
    return dp[n]

print(f"Anzahl der Möglichkeiten, zur 5. Stufe zu steigen (DP): {climb_stairs_dp(5)}")  # Ausgabe: 8

Methode 4: Speicheroptimierung (rollendes Array)

Beobachte die Zustandsübergangsgleichungdp[i] = dp[i-1] + dp[i-2], stellen wir fest, dass der aktuelle Zustand nur von den beiden vorherigen Zuständen abhängt. Daher müssen wir nicht das gesamtedpArray speichern; verwenden Sie einfach zwei Variablen, um sie rollierend zu aktualisieren.

Beispiel

def climb_stairs_optimized(n: int) -> int:
    """Dynamische Programmierung (speicheroptimierte Version)"""
    if n <= 2:
        return n
    # Verwenden Sie nur zwei Variablen, um dp[i-1] und dp[i-2] darzustellen
    prev, curr = 1, 2  # Entsprechen dp[1], dp[2]
    for i in range(3, n + 1):
        # Den neuen aktuellen Wert berechnen
        new_curr = prev + curr
        # Variablen rollierend aktualisieren, Vorbereitung für die nächste Schleifeniteration
        prev, curr = curr, new_curr
    return curr

print(f"Anzahl der Möglichkeiten, zur 5. Stufe zu gelangen (optimierte DP): {climb_stairs_optimized(5)}")  # Ausgabe: 8

Nach der Optimierung fällt die Speicherkomplexität vonO(n)aufO(1)。

Problemlösungsframework für dynamische Programmierung

Mithilfe des Treppensteigproblems können wir einen allgemeingültigen Vier-Schritt-Prozess zur Lösung von Problemen der dynamischen Programmierung zusammenfassen:

Schritt 1: Den Zustand definieren

Verwenden Sie ein oder mehrere Arrays (normalerweise genanntdp) um die Lösungen von Teilproblemen darzustellen. Der Schlüssel liegt darin, klar herauszufinden:dp[i]oderdp[i][j]Was repräsentiert es?

Beim Treppensteigproblem definieren wirdp[i]als "Aufstieg zuridie Gesamtzahl der Möglichkeiten, Stufe n zu erreichen.

Schritt 2: Die Zustandsübergangsgleichung bestimmen

findedp[i]mit dem vorherigen Zustand (wie z. B.dp[i-1], dp[i-2]die Beziehung zwischen ihnen. Dies ist der Kern und die Schwierigkeit der dynamischen Programmierung.

Beim Treppensteigen-Problem lautet die Zustandsübergangsgleichung:dp[i] = dp[i-1] + dp[i-2]。

Schritt 3: Bestimme die Anfangsbedingungen (Basisfall).

Die Lösungen der kleinsten, unteilbaren Teilprobleme. Dies ist der Ausgangspunkt der Rekurrenz und muss manuell definiert werden.

Beim Treppensteigen-Problem lauten die Anfangsbedingungen:dp[1] = 1, dp[2] = 2。

Schritt 4: Bestimme die Berechnungsreihenfolge und berechne

Bestimme, ob es sich um "Top-down" (memoisierte Rekursion) oder "Bottom-up" (iterative Rekurrenz) handelt, und stelle sicher, dass beim Berechnen vondp[i], alle Teilprobleme, von denen es abhängt, bereits berechnet wurden.

Beim Treppensteigen-Problem verwenden wir einen Bottom-up-Ansatz und beginnen beii=3Schleife bisi=n。

Klassisches Beispiel: Fibonacci-Folge

Die Fibonacci-Folge ist das direkteste Beispiel für dynamische Programmierung; ihre Definition selbst ist die Zustandsübergangsgleichung.

Problem: Finde die n-te Fibonacci-ZahlnGlied.F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)

Beispiel

def fibonacci(n: int) -> int:
    """Berechne Fibonacci-Zahlen mit dynamischer Programmierung"""
    if n < 2:
        return n
    # Speicheroptimierte Implementierung
    prev, curr = 0, 1  # F(0), F(1)
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Testdaten
test_n = 10
print(f"Das {test_n}. Glied der Fibonacci-Folge ist: {fibonacci(test_n)}")  # Ausgabe: 55

Fortgeschrittenes Beispiel: Münzwechsel

Dies ist ein typischeres Problem, das optimale Teilstruktur demonstriert.

Problembeschreibung: Gegeben ist ein ganzzahliges Arraycoins, das Münzen unterschiedlicher Nennwerte repräsentiert, und eine Ganzzahlamount, die den Gesamtbetrag repräsentiert. Berechne und gib die minimale Anzahl von Münzen zurück, die benötigt wird, um den Gesamtbetrag zu bilden. Wenn keine Kombination von Münzen den Gesamtbetrag bilden kann, gib-1. Du kannst annehmen, dass die Menge jeder Münze unbegrenzt ist.

Problemanalyse und DP-Design

  1. Zustand definieren：dp[i]steht für das Bilden des Gesamtbetragsidie minimale Anzahl benötigter Münzen.
  2. Zustandsübergangsgleichung: Für den Betragi, können wir über jeden Münznennwert iterierencoin. Wenncoin <= i, dann den Betrag bildeniEine mögliche Vorgehensweise ist: zuerst den Betrag bildeni - coin, dann eine Münze hinzufügencoinNennwert der Münze. Was wir finden müssen, ist das Minimum unter allen Möglichkeiten. Daher kann die Gleichung geschrieben werden als:dp[i] = min(dp[i], dp[i - coin] + 1), für alle, die erfüllencoin <= ivoncoin。
  3. Anfangsbedingungen：dp[0] = 0, das Bilden von Betrag 0 erfordert 0 Münzen. Die anderendp[i]auf eine sehr große Zahl initialisiert (z. B.amount + 1oderfloat('inf')), was bedeutet, dass er vorerst nicht gebildet werden kann.
  4. Berechnungsreihenfolge: von unten nach oben, voni=1Berechne bisi=amount。

Code-Implementierung

Beispiel

def coin_change(coins: list, amount: int) -> int:
    """Münzwechsel - Dynamische Programmierung"""
    # Initialisiere das dp-Array, wobei dp[i] die minimale Anzahl an Münzen für Betrag i darstellt
    # Setze einen unerreichbaren Anfangswert amount + 1
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # Wenn der Betrag 0 ist, werden 0 Münzen benötigt
   
    # Äußere Schleife: über alle Betragszustände iterieren
    for i in range(1, amount + 1):
        # Innere Schleife: über alle Münzoptionen iterieren
        for coin in coins:
            # Wenn der aktuelle Münznennwert kleiner oder gleich dem aktuellen Betrag ist, die Verwendung dieser Münze in Betracht ziehen
            if coin <= i:
                # Zustandsübergang: dp[i] ist die Lösung ohne Verwendung der aktuellen Münze und
                # der kleinere Wert unter den Lösungen, die die aktuelle Münze verwenden (d. h. dp[i-coin] + 1)
                dp[i] = min(dp[i], dp[i - coin] + 1)
   
    # Wenn dp[amount] nicht aktualisiert wurde (noch der Anfangswert), bedeutet das, dass der Betrag nicht gebildet werden kann
    return dp[amount] if dp[amount] <= amount else -1

# Testdaten
coins = [1, 2, 5]
amount = 11
print(f"Die minimale Anzahl an Münzen, die benötigt wird, um den Gesamtbetrag {amount} zu bilden, ist: {coin_change(coins, amount)}")  # Ausgabe: 3 (5+5+1)

Übungsaufgaben

Bitte versuchen Sie, die folgenden Probleme selbstständig zu lösen, um Ihr Verständnis der dynamischen Programmierung zu festigen:

Übung 1: Maximale Teilsumme

Gegeben ist ein ganzzahliges Arraynums, bitte finden Sie ein zusammenhängendes Teilarray mit der maximalen Summe und geben Sie dessen maximale Summe zurück.

Beispiel：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6.

Hinweis：

  • Definitiondp[i]als "mit deridie maximale Summe eines zusammenhängenden Teilarrays, das mit dem Element endet".
  • Zustandsübergangsgleichung:dp[i] = max(nums[i], dp[i-1] + nums[i])。
  • Die endgültige Antwort ist allesdp[i]das Maximum unter ihnen.

Übung 2: Längste aufsteigende Teilfolge

Gegeben ist ein ganzzahliges Arraynums, finde die Länge der längsten streng monoton steigenden Teilfolge.

Beispiel：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4.

Hinweis：

  • Definitiondp[i]als "mit deridie Länge der längsten aufsteigenden Teilfolge, die mit der Zahl endet".
  • Für jedesi, muss man durchlaufenjfrom0aufi-1, wennnums[i] > nums[j], danndp[i] = max(dp[i], dp[j] + 1)。
  • Anfangs enthält jededp[i]mindestens 1 (enthält nur sich selbst).
Weitere Erweiterungen