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。