algorithm - 在多项式时间内计算Scheme中两个列表的最长公共(public)子序列

Question

所以我需要计算两个列表的最长公共(public)子序列，但是需要在多项式时间内。我遇到的唯一问题是我不允许使用“!”根本。这意味着我无法使用 set! 更改 vetcor 或列表的值。我找不到不需要二维列表或某种数组的多项式算法。有人有什么想法吗？

Answer 1

您不需要使用 set!(或任何其他变异操作)来使用 2d 列表或向量。

您可以对二维向量使用标准动态规划算法，但不是更改向量以插入您为给定单元格计算的值，而是使用 build-vector 创建一个新向量这与旧版本相同，只是您更改了给定位置的值。

这是非常低效的，但仍然是多项式的，我认为如果没有惰性或变异，不可能真正有效地做到这一点。

编辑:使用 build-vector 来执行此操作，看起来像这样:

(build-vector n (lambda (i)
  (build-vector n (lambda (j)
    (if (and (= i x) (= j y))
        new-value
        (vector-ref (vector-ref old-vector i) j))))))

其中old-vector是你要复制的n*n向量，你要替换位置x,y的值> 值为 new-value。 (注意:在现实生活中使用这样的函数几乎总是一个错误，因为正如我所说，这是非常低效的)。