algorithm - longest common subsequence with linear memory usage

Question

I'm trying to find an algorithm which uses linear space of memory for:

Given two strings x and y over an arbitrary alphabet, determine their longest common sub sequence.

Answer 1

请注意，当您在动态规划解决方案中计算表格的下一行以解决 LCS 问题时，您只需要前一行和当前行。然后您可以修改动态编程解决方案以仅跟踪前一行和当前行而不是 mxn 表。每次到达当前行的末尾时，将上一行设置为当前行，并再次从行的开头开始。您这样做 m 次，其中 m 是表中的行数。这将在列数中使用空间线性。