DP auf LeetCode: 3 Probleme mit Rezessionsformeln

Dynamische Programmierung: Ein intuitiver Ansatz für drei LeetCode-Aufgaben

Dynamische Programmierung (DP) löst Zähl- und Optimierungsprobleme durch Rekursionsbeziehungen. Betrachten wir die Aufgaben 62 (Unique Paths), 64 (Minimum Path Sum) und 70 (Climbing Stairs). Jede zeigt Schlüsselmerkmale der DP: optimale Unterstruktur und überlappende Teilprobleme.

Unique Paths: Routen auf einem Gitter zählen

Ein Roboter bewegt sich auf einem m × n Gitter von (0,0) nach (m-1,n-1) und kann nur nach rechts oder unten gehen. Finde die Anzahl der eindeutigen Pfade.

Jeder Pfad besteht aus (m-1) Schritten nach unten und (n-1) Schritten nach rechts. Eine kombinatorische Lösung nutzt den Binomialkoeffizienten C(m+n-2, m-1). In Interviews wird jedoch ein algorithmischer Ansatz erwartet.

Definiere dp[i][j] als die Anzahl der Pfade zur Zelle (i,j). Rekursionsbeziehung:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Randbedingungen:

• dp[0][j] = 1 (erste Zeile)
• dp[i][0] = 1 (erste Spalte)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

Zeitkomplexität O(m·n). Die Lösung nutzt die Additionsregel für disjunkte Pfadmengen.

Minimum Path Sum: Minimierung der Pfadkosten

Gegeben ein m × n Gitter mit nicht-negativen Zahlen. Finde die minimale Summe der Werte auf einem Pfad von (0,0) nach (m-1,n-1) bei Bewegung nach rechts oder unten.

Ein Greedy-Algorithmus (lokales Minimum wählen) scheitert – er führt zu Sackgassen mit hohen Werten. Globale Optimierung ist erforderlich.

Definiere dp[i][j] als die minimalen Kosten, um (i,j) zu erreichen. Rekursionsbeziehung:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Randbedingungen:

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

Komplexität O(m·n). Jeder Wert wird für alle nachfolgenden Zellen verwendet.

Climbing Stairs: Fibonacci-Zahlen in der DP

Treppensteigen mit n Stufen (1 ≤ n ≤ 45), jede Stufe ist 1 oder 2 Stufen. Finde die Anzahl der Möglichkeiten.

Für n=1: 1 Möglichkeit

n=2: 2 Möglichkeiten (1+1, 2)

n=3: 3 Möglichkeiten (1+1+1, 1+2, 2+1)

Rekursionsbeziehung:

dp[n] = dp[n-1] + dp[n-2]

Einfache Rekursion führt zu exponentieller Komplexität O(φ^n) durch wiederholte Berechnungen. Ein DP-Array löst das Problem:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Eine optimierte Version nutzt O(1) Speicher mit zwei Variablen.

Anzeichen für Dynamische Programmierung Probleme

Wende DP an, wenn zwei Bedingungen erfüllt sind:

• Optimale Unterstruktur: Die optimale Lösung besteht aus optimalen Lösungen für Teilprobleme.
• Überlappende Teilprobleme: Dieselben Teilprobleme werden mehrfach berechnet.

| Problem | Optimale Unterstruktur | Überlappende Teilprobleme |

|--------|-------------------------|---------------------------|

| Unique Paths | Summe der Pfade von benachbarten Zellen | Jeder Pfad zu einer Zelle überlappt |

| Min Path Sum | Minimale Kosten von Nachbarn | Kosten werden für alle Zellen unten/rechts verwendet |

| Climbing Stairs | Summe von n-1 und n-2 | Rekursive Aufrufe wiederholen sich |

Wichtige Erkenntnisse

• Rekursionsbeziehungen definieren das Wesen der DP: dp[i][j] hängt nur von bereits berechneten benachbarten Werten ab.
• Randbedingungen werden separat für die erste Zeile/Spalte oder Basisfälle gefüllt.
• Zeitkomplexität ist bei korrekter tabellarischer Implementierung immer O(Eingabegröße).
• Speicher kann optimiert werden: für Gitter – eine Zeile, für lineare Probleme – zwei Variablen.
• Kombinatorik bietet oft einen mathematischen Abkürzung, aber algorithmische Lösungen sind für Interviews wichtiger.

— Editorial Team