Algorithmen und Datenstrukturen · Senior · Frage 27 von 75
Wie senkt man den Speicher einer DP für LCS oder Edit-Distanz von O(n × m) auf O(m)?
- 1Die Tabelle in einer
Mapstatt einem Array speichern - 2Rekursion ohne Cache nutzen
- 3Nur die vorige Zeile behalten, da jede Zelle davon abhängt
Antwort zeigen
Richtige Antwort: Nur die vorige Zeile behalten, da jede Zelle davon abhängt
Erklärung
Zelle (i, j) braucht nur (i-1, j), (i, j-1) und (i-1, j-1). Zwei Zeilen (oder eine mit gemerkter Diagonale) reichen für die Länge. Die eigentliche Zuordnung zu rekonstruieren braucht dann zusätzliche Arbeit, etwa Hirschbergs Algorithmus.