Algorytmy i struktury danych · Senior · Pytanie 27 z 75
Jak zmniejszyć pamięć DP dla LCS lub odległości edycyjnej z O(n × m) do O(m)?
- 1Przechowywać tabelę w
Mapzamiast w tablicy - 2Użyć zwykłej rekurencji bez zapamiętywania
- ✓Poprawna odpowiedź: Trzymać tylko poprzedni wiersz tabeli
Wyjaśnienie
Komórka (i, j) potrzebuje tylko (i-1, j), (i, j-1) i (i-1, j-1). Do długości wystarczą dwa wiersze (albo jeden z zapamiętaną przekątną). Odtworzenie samego dopasowania wymaga wtedy dodatkowej pracy, np. algorytmu Hirschberga.