Algorithms and Data Structures · Senior · Question 27 of 75
How do you reduce the memory of an LCS or edit distance DP from O(n × m) to O(m)?
- 1Store the table in a
Mapinstead of an array - 2Use recursion without a cache
- ✓Correct answer: Keep only the previous row, since each cell depends on it
Explanation
Cell (i, j) needs only (i-1, j), (i, j-1) and (i-1, j-1). Two rows (or one with a saved diagonal) are enough for the length. Reconstructing the actual alignment then needs extra work, for example Hirschberg's algorithm.