algorithm - 一维动态规划的懒惰打结

Question

几年前，我参加了一门算法类(class)，我们给出了以下问题(或类似的问题):

There is a building of n floors with an elevator that can only go up 2 floors at a time and down 3 floors at a time. Using dynamic programming write a function that will compute the number of steps it takes the elevator to get from floor i to floor j.

使用有状态方法显然很容易，您可以创建一个长度为 n 个元素的数组并用值填充它。您甚至可以使用技术上无状态的方法，该方法涉及通过递归传递结果来累积结果。我的问题是如何通过使用惰性求值和打结来以无状态方式执行此操作。

我想我已经设计了正确的数学公式:



哪里 i+2和 i-3在允许的值内。

不幸的是，我无法让它终止。如果我把 i+2案例第一然后选择一个偶数楼层我可以得到它来评估目标水平以下的偶数楼层，但就是这样。我怀疑它会直接射到最高的均匀楼层，然后下降 3 个级别，然后重复，永远在前几层之间振荡。

所以它可能是以深度优先的方式探索无限空间(或有限但有循环)。我想不出如何以广度优先的方式探索空间，而不使用大量有效模仿有状态方法的数据结构。

虽然这个简单的问题令人失望地困难，但我怀疑在 1 维中看到了一个解决方案，我可能能够使它适用于问题的 2 维变化。

编辑:很多答案都试图以不同的方式解决问题。问题本身对我来说并不有趣，问题在于使用的方法。 Chaosmatter 创建 minimal 的方法可以比较潜在无限数字的函数可能是朝着正确方向迈出的一步。不幸的是，如果我尝试创建一个代表具有 100 层楼的建筑物的列表，则结果需要很长时间来计算，因为子问题的解决方案没有被重用。

我尝试使用自引用数据结构，但它没有终止，存在某种无限循环。我将发布我的代码，以便您了解我要做什么。如果有人实际上可以在自引用数据结构上使用动态编程解决问题，使用懒惰来避免多次计算事物，我将更改已接受的答案。

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (\n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

你可以看看如何 1 + levels !! i尝试引用先前计算的结果以及如何 filter (\n -> n >= 0 && n <= 10) [x+2,x-3]试图限制 i 的值到有效的。正如我所说，这实际上不起作用，它只是演示了 方法 我希望看到这个问题得到解决。其他解决方法是 不是 对我来说很有趣。

Answer 1

问题是min需要全面评估对 f 的两次调用,
所以如果其中一个无限循环 min永远不会回来。
因此，您必须创建一个新类型，对 f 返回的数字进行编码。是零或零的后继者。

data Natural = Next Natural 
             | Zero

toNum :: Num n => Natural -> n
toNum Zero     = 0
toNum (Next n) = 1 + (toNum n)

minimal :: Natural -> Natural -> Natural
minimal Zero _            = Zero
minimal _ Zero            = Zero
minimal (Next a) (Next b) = Next $ minimal a b

f i j | i == j = Zero
      | otherwise = Next $ minimal (f l j) (f r j)
      where l = i + 2
            r = i - 3

这段代码确实有效。