線性內存使用

Question

我試圖找到其使用的內存線性空間的算法最長公共子。

Answer 1

請注意，當您在動態編程解決方案中計算表格的下一行以解決LCS問題時，您只需要上一行和當前行。然後，您可以修改動態編程解決方案來跟蹤僅前一行和當前行，而不是m x n表。每當到達當前行的末尾時，就將前一行設置爲當前行，然後再次從行的開始處開始。你這樣做m次，其中m是表中的行數。這將在列數中使用空間線性。