如何改进该算法 (LCS)

Question

  (define (lcs lst1 lst2)
   (define (except-last-pair list)
   (if (pair? (cdr list))
   (cons (car list) (except-last-pair (cdr list)))
   '()))
  (define (car-last-pair list)
   (if (pair? (cdr list))
   (car-last-pair (cdr list))
   (car list)))
  (if (or (null? lst1) (null? lst2)) null
   (if (= (car-last-pair lst1) (car-last-pair lst2))
      (append (lcs (except-last-pair lst1) (except-last-pair lst2)) (cons (car-last-pair lst1) '()))
      (**if (> (length (lcs lst1 (except-last-pair lst2))) (length (lcs lst2 (except-last-pair lst1)))) 
          (lcs lst1 (except-last-pair lst2))
          (lcs lst2 (except-last-pair lst1))))))**

我不想让它一遍又一遍地运行..

问候， 超级守护者

Answer 1

我发现这应该采用两个列表的最长公共子序列。正如您所指出的，它非常慢。如果你想让它更快地工作，你需要采取一种更复杂的方法，而不仅仅是像这样暴力破解；规范的解决方案是这篇维基百科文章中描述的动态规划算法。

无需完全切换到不同算法即可大大加快解决方案速度的一种方法是通过记忆结果，因为就目前情况而言，当您递归并从列表末尾删除元素时，您将一遍又一遍地计算相同的中间结果。

编辑：嗯，一种简单的方法，使其更快一点，而不需要太多工作，就是使用 let 子句来避免底部的额外工作，即

(if (or (null? lst1) (null? lst2)) null
  (let ((front1 (except-last-pair lst1)) (front2 (except-last-pair lst2)))
    (if (= (car-last-pair lst1) (car-last-pair lst2))       
      (append (lcs front1 front2) (cons (car-last-pair lst1) '()))
      (let ((sub-lcs1 (lcs lst1 front2)) (sub-lcs2 (lcs lst2 front1)))
        (if (> (length sub-lcs1) (length sub-lcs2)) 
          sub-lcs1
          sub-lcs2))))

希望它是正确的 - 我没有解释器方便 - 但你明白了。