Алгоритми та структури даних · Senior · Запитання 27 з 75
Як зменшити пам'ять DP для LCS чи редакційної відстані з O(n × m) до O(m)?
- 1Зберігати таблицю в
Mapзамість масиву - 2Використати рекурсію без жодного кешу
- ✓Правильна відповідь: Тримати лише попередній рядок таблиці
Пояснення
Клітинці (i, j) потрібні лише (i-1, j), (i, j-1) і (i-1, j-1). Для довжини вистачить двох рядків (або одного зі збереженою діагоналлю). Відновлення самого вирівнювання тоді потребує додаткової роботи, наприклад алгоритму Гіршберга.