Lisp 可以实现自下而上的动态规划吗？

Question

典型的 Lisp 方言可以使用自下而上的“动态编程”方法解决问题吗？

（请注意：我不是在谈论“记忆化”，据我所知，使用任何 Lisp 方言都是微不足道的。我真正谈论的是自下而上的动态编程，您可以在其中构建，例如，您的数组自下而上，然后使用您刚刚引入的元素来计算下一个元素。）

例如，使用动态规划，可以解决“0-1背包”问题输入的伪多项式时间任何其他方法都会失败。

一个命令式（不完整）的解决方案是：

for (int k = 1; k <= a.length; k++) {
    for (int y = 1; y <= b; y++) { 
        if (y < a[k-1]) {
            knap[k][y-1] = knap[k-1][y-1];
        } else {
            if (y > a[k-1]) {
                knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
            } else {
                knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
    }
}

在各种 Lisp 方言中是否可以做到这样的事情？如果不是，为什么不呢？

Answer 1

当然这是可能的。您唯一需要的是数组、整数和循环结构。例如，在Scheme中，您的算法可以使用 向量。主要问题是它变得难以阅读，因为 knap[k-1][y-1] 变成 (vector-ref (vector-ref knap (- k 1)) ( - y 1)) 并

knap[k][y-1] = knap[k-1][y-1];

成为

(vector-set! (vector-ref knap k) (- y 1)
             (vector-ref (vector-ref knap (- k 1)) (- y 1)))

（或带有模数的毛茸茸的技巧），而记忆的递归只是保持可读。

根据经验，我建议您在使用 Lisp 和类似语言编程时坚持记忆。如果使用哈希表，则记忆化和 DP 的预期渐近时间和空间复杂度是相同的。

Answer 2

简短的回答是肯定的，Clojure 可以直接使用 java 数组，所以直接翻译
非常简单，

 (for [k (range 1 (count a)) 
       y (range 1 b)]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                                 (aget c (dec k))))))))))

这不是很理想的 Clojure，因为它将循环与要完成的工作结合在一起。
如果您将此循环的元素分开，则生成的代码将更加清晰且更容易显示正确性。

作为一个简单的第一步，如果我们将循环与“工作”分开，那么我们就会得到。

(defn edit-array [k y]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                             (aget c (dec k))))))))))
(for [k (range 1 (count a)) y (range 1 b)]
   (edit-array k y))

然后我们可以从 repl 测试编辑数组，并让我们自己相信它可以工作（也许还可以编写一个单元测试）。之后，也许您想开始更仔细地查看 edit-array 并决定是否可以将其分解为更容易独立测试的步骤。也许您可以更改它以使用函数式风格而不是改变数组。在这里，我将不再讨论您的具体问题，因为我不得不承认，我不理解这个线性规划解决方案旨在解决的原始问题。

 (defn finished? [row] ... determine if we have reached the final state ...)

 (defn next-row [current-row]
    (for [y (range 1 (count current-row)]
      ... code to produce a new vector based on the previous one ...))

(take-while #(not (finished? %) (iterate next-row (initial-state)))

我所看到的 Idomatic Clojure 代码的基本概念是将问题分解为简单的（只做一件事）抽象，然后组合它们来解决主要问题。当然，这必须始终根据当前的问题进行定制。

Answer 3

请原谅我这样说，但是您引用的维基百科页面（imnsho）写得不是很好。特别是，它或多或少地制造了自上而下和自下而上的动态规划之间的二分法，并继续将其描述为“更有趣”。两者之间的唯一区别是构建表的顺序。记忆化会产生这两种情况，具体取决于调用的顺序。

提前向撰写该页面这一部分的人致歉；我感谢您的努力，我只是认为该部分需要一些工作。

Answer 4

这是 Clojure 中斐波那契的一个很好的自下而上版本（我相信最初是由 Christophe Grand 编写的）：

(defn fib []
  (map first (iterate
              (fn [[a b]] [b (+ a b)])
              [0 1])))

这会生成一个无限的惰性序列，因此您可以根据自己的喜好要求任意多或少：

(take 10 (fib))
=> (0 1 1 2 3 5 8 13 21 34)

(nth (fib) 1000)
=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875