algorithm - Haskell:递归定义的函数值的有效计算

Question

我想计算递归定义的函数值r(i,j)，它们由

定义

r i j  | i<0 || j<0   = 0
       | i==0 && j==0 = 1
       | otherwise    = (i-1) * r (i-2) j + r (i-1) (j-1)

显然，这些系数的 NxN 表可以在 O(N^2) 中计算。 不幸的是，直截了当的评价，比如

[[r i j | j <-[0..50]]| i <- [0..50]]

以非常低效的方式执行(指数复杂度)。显然，Haskell 为每个 r i j 构建了整个递归树，并忽略了先前计算的 r (i-1) (j-1) 等的值。

计算这样一个表的优雅而有效的方法是什么？

Answer 1

正如 FUZxxl 所说，这是一个内存问题。

r i j | i < 0 || j < 0 = 0
      | otherwise      = rss !! i !! j

rss = [[r' i j | j <- [0..]] | i <- [0..]]
  where r' 0 0 = 1
        r' i j = (i-1) * r (i-2) j + r (i-1) (j-1)

如果您需要一个精确到 50 的值的显式表，您可以使用 take 51 (map (take 51) rss) , 或 [[r i j | j <-[0..50]]| i <- [0..50]]正如你提到的。否则你可以调用r或引用 rss直接。