我正在努力记住如何在懒惰球拍中进行动态编程。在我解决了Project Euler的一个问题后，我开始对此感到好奇：
从下面三角形的顶部开始，移动到相邻的下面一行的数字，从上到下的最大总数为23。
3 7 4 2 4 6 8 5 9 3也就是说，3+7+4+9＝23。
从下面三角形的顶部到底部求出最大总和：…
我用下面的代码解决了这个问题。然而，我在学校里学到了懒惰球拍(事实上，还有一般的编程语言)，我似乎记得在懒惰语言中，解决动态编程问题要容易得多。例如，在其他欧拉主义者发布的解决方案中，有人发布了他用来解决问题的haskell代码，而实际指定问题中的数据(三角形本身是什么)只需要一行代码。然而，我不理解代码，所以我仍然很困惑。
摘要：
- 如何解决懒惰球拍中的动态编程问题？例如，答案可能会解决上面给出的4级三角形示例(而不是完整的15级三角形)问题，或者发布一些以前制作的编辑距离代码(这就是我学习DP的方式)
- 为什么用惰性语言(比如惰性球拍)进行动态编程更容易
下面给出了我用来解决常规球拍中DP问题的80行代码。
#lang racket
(define (triangle-ref x y)
(let ((triangle
(vector-immutable
(vector-immutable 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)
(vector-immutable 63 66 04 68 89 53 67 30 73 16 69 87 40 31)
(vector-immutable 91 71 52 38 17 14 91 43 58 50 27 29 48)
(vector-immutable 70 11 33 28 77 73 17 78 39 68 17 57)
(vector-immutable 53 71 44 65 25 43 91 52 97 51 14)
(vector-immutable 41 48 72 33 47 32 37 16 94 29)
(vector-immutable 41 41 26 56 83 40 80 70 33)
(vector-immutable 99 65 04 28 06 16 70 92)
(vector-immutable 88 02 77 73 07 63 67)
(vector-immutable 19 01 23 75 03 34)
(vector-immutable 20 04 82 47 65)
(vector-immutable 18 35 87 10)
(vector-immutable 17 47 82)
(vector-immutable 95 64)
(vector-immutable 75))))
(vector-ref (vector-ref triangle y) x)))
(define triangle-size 15)
(define (problem18)
(let ((table (let fill-table ((table (hash))
(current-x 0)
(current-y 0))
(cond ((>= current-y triangle-size) table)
((>= current-x (- triangle-size current-y))
(fill-table table 0 (add1 current-y)))
(else (let ((reference (cons current-x current-y))
(triangle-value (triangle-ref current-x
current-y)))
(if (= current-y 0)
(fill-table (hash-set table
reference
(cons triangle-value
empty))
(add1 current-x)
current-y)
(let* ((left-entry (hash-ref
table
(cons
current-x
(sub1 current-y))))
(left-cost (car left-entry))
(left-path (cdr left-entry))
(right-entry (hash-ref
table
(cons
(add1
current-x)
(sub1
current-y))))
(right-cost (car right-entry))
(right-path (cdr right-entry)))
(if (> left-cost right-cost)
(fill-table (hash-set table
reference
(cons
(+ triangle-value
left-cost)
(cons
triangle-value
left-path)))
(add1 current-x)
current-y)
(fill-table (hash-set table
reference
(cons
(+ triangle-value
right-cost)
(cons
triangle-value
right-path)))
(add1 current-x)
current-y))))))))))
(car (hash-ref table (cons 0 (sub1 triangle-size))))))
(problem18)
(provide problem18)
对于某些类型的问题，懒惰可以让你以一种良好的、模块化的方式组织你的解决方案，你可以首先像生成每一个可能的解决方案一样编写代码(即使有无限的可能性)，然后单独编写代码来测试解决方案是否是有效的解决方案。在懒惰的语言中，这样的算法只会检查足够的可能解决方案来计算最终结果，而所有其他可能性自然不会被计算出来，因此它与回溯等更复杂的策略一样有效。
一个典型的例子是解决数独难题的算法(谷歌搜索会发现很多例子)。你可能还对约翰·休斯的一篇论文感兴趣，该论文名为"为什么函数编程很重要"。
话虽如此，在这种特殊情况下，懒惰并没有多大帮助。无论是热切的语言还是懒惰的语言，动态编程风格的解决方案都会很好地工作(并且看起来大致相同)。
当解决这样的问题时，通常先计算一个朴素的解决方案，然后改进它是有帮助的。朴素的解决方法会计算出所有可能的总数，然后取最大值。对于小三角形的例子，你可以计算3+7+2+8、3+7+2+5等，但只要把它写下来，就会发现一个可能的改进，因为3+7+2是重复的。避免这些类型的重复计算正是动态编程所做的。动态算法将只计算这些中间结果一次，然后重复使用多次。
我们通过一次一行地递增计算最大总数来实现这一点。以这种方式计算最大总数的函数可能如下所示：
(注意：您需要安装最新的夜间版本才能运行此Racket代码。)
;; A Row is a list of at least one number.
;; A Triangle is a list of at least one Row,
;; where each row has one more number than the previous row.
;; ----------------------------------------------------------------------------
;; top-down solution
;; max-tri-route : Triangle -> Number
;; Computes the maximum total when moving from top of triangle to bottom.
(define/match (max-tri-route tri)
[((list a-single-row))
(apply max a-single-row)]
[((list-rest row1 row2 rest-rows))
(max-tri-route (cons (process-row row1 row2) rest-rows))])
我假设一个三角形用一个列表列表来表示，其中每个子列表代表一行。我们假设三角形的第一行代表我们递增计算的总数。这个函数表示，如果只有一行，则取该行的最大值。否则，使用第一行(到目前为止的总数)和第二行调用流程行函数。处理行函数将第二行合并到中间总计中，可能看起来像这样：
;; process-row : Row Row -> Row
;; Takes a list of intermediate maximum values and a row, and incorporates
;; the given row into the intermediate values.
;; - new-row always has one more element than tmp-maxes
;; - produces list of length new-row
(define/match (process-row tmp-maxes new-row)
[((list x) (list y z))
(list (+ x y) (+ x z))]
[((list-rest x rest-maxes) (list-rest y z rest-row))
(define res (process-row rest-maxes (cons z rest-row)))
(cons (+ x y) (cons (max (+ x z) (first res)) (rest res)))])
此函数假定第二个给定行总是比第一个给定行多出一个数字。如果给定的两行分别只有一个和两个数字，那么只需将第一行的数字与第二行的每个数字相加即可。否则，我们通过一次考虑三个数字来计算新的中间总数：第一行中的一个数字和第二行中的两个相邻数字。当然，第二行中的每个数字(除了末端)都有两个来自第一行的相邻数字，所以我们只想取较大的一个。例如，在小三角形示例中，调用前两行上的处理行会产生中间值10和7。然后，如果进程行用10 7调用，下一行用2 4 6调用，它首先考虑10用2和4，产生12和14。但它也必须考虑7和下面的4。由于7+4=11小于14，所以我们保留的中间总数是14。合并第三行之后得到的中间总数是12 14 13。
即使对于问题67中的三角形，上述解决方案也能有效地得出正确答案。但这感觉有点尴尬，尤其是在流程行的第二部分，我们必须考虑重叠的案例。让我们看看是否可以使解决方案变得更好。
Take#2：
在第一个解决方案中，由于我们从上到下处理三角形，我们的中间总计列表会随着每一行的增加而增加。但最后我们必须计算所有中间值的最大值。但没有任何东西表明我们必须从上到下处理三角形。由于我们只对总数感兴趣，所以自下而上我们会得到相同的答案。让我们看看这会是什么样子：
;; ----------------------------------------------------------------------------
;; bottom-up solution
(define (max-tri-route2 tri) (max-tri/bottom-up (reverse tri)))
;; Computes total starting from bottom row.
(define/match (max-tri/bottom-up tri)
[((list (list the-max-total)))
the-max-total]
[((list-rest row1 row2 rest-rows))
(max-tri/bottom-up (cons (process-row/bottom-up row2 row1) rest-rows))])
;; - tmp-maxes always has one more element than new-row
;; - produces list of length new-row
(define/match (process-row/bottom-up new-row tmp-maxes)
[((list x) (list y z))
(list (+ x (max y z)))]
[((list-rest x rest-row) (list-rest y z rest-maxes))
(cons (+ x (max y z)) (process-row/bottom-up rest-row (cons z rest-maxes)))])
对于自下而上的方法，我们在最后只有一个值，即最终答案。此外，流程行/自下而上比流程行更简单，因为我们现在可以直接保留两个数字中较大的一个。
然而，我们可以做得更好。
取#3：
这种在列表上迭代并累积中间值的模式非常常见，因此有内置的函数可以做到这一点：foldr和foldl。这些函数中的每一个都有一个要遍历的列表、一个初始中间值，以及一个将列表中的下一个值与当前中间值组合的函数。但是我们需要什么组合功能呢？事实证明，这正是我们的流程行函数。以下是foldl:的解决方案
;; ----------------------------------------------------------------------------
;; bottom-up, with foldl
(define (max-tri-route3 tri)
(define rev-tri (reverse tri))
(first (foldl process-row/bottom-up (first rev-tri) (rest rev-tri))))
foldl从列表的左边开始，但由于我们想自下而上，我们首先颠倒列表。我们使用第一行(即底部)作为初始中间值，其余行作为三角形。完成后，我们将有一个值列表，即答案。
Take#4：
最后一次改进。为什么我们要把三角形倒过来，然后从左边开始。为什么我们不从右边开始使用foldr，使用最后一行作为初始累加器？foldr的问题是，我们必须显式指定一个初始累加器，但像Haskell这样的一些语言有一个内置函数foldr1，它会自动使用列表的最后一个元素作为初始中间值。Racket没有，但我们可以很容易地实现它。
;; ----------------------------------------------------------------------------
;; bottom-up, with foldr1
(define/match (foldr1 f lst)
[(_ (list x)) x]
[(_ (list-rest x rest)) (f x (foldr1 f rest))])
(define (max-tri-route4 tri) (first (foldr1 process-row/bottom-up tri)))
当然，foldr1函数假设您给它的列表至少有一个元素。有了foldr1函数，并使用以前的处理行/自下而上的函数，我们的解决方案现在是一个单行函数。这可能也是您看到的Haskell解决方案的样子。
有关包含此代码的完整程序，请参阅此处。