尝试为 Haskell 中的函数创建有效的算法

我正在寻找一种有效的多项式时间解决方案来解决以下问题：

实现一个递归函数节点 x y 来计算数字三角形中的第 (x,y) 个数字，定义为

g(x,y) = 0 if |x| > y
       = 1 if (x,y) = (0,0)
       = sum of all incoming paths otherwise

到节点的所有传入路径的总和定义为从根节点 (x, y) = (0, 0) 到所考虑的节点的所有可能路径值的总和，其中在每个节点 (x,y ) 路径可以沿对角线向下和向左 (x−1,y+1)、直线向下 (x,y+1) 或对角线向下和向右 (x+1,y+1) 继续。到节点的路径的值定义为沿该路径直至（但不包括）所考虑的节点的所有节点的总和。

数字三角形中的前几个条目在表中给出：

\  x  -3  -2  -1  0  1  2  3 
 \  
y \ _________________________
   |
0  |   0   0   0  1  0  0  0
   |
1  |   0   0   1  1  1  0  0
   |
2  |   0   2   4  6  4  2  0
   |
3  |   4   16  40 48 40 16 4

我试图首先找到一个简单的解决方案，这就是我所拥有的：

node x y | y < 0                = error "number cannot be negative"
         | (abs x) > y          = 0
         | (x == 0) && (y == 0) = 1
         | otherwise            = node (x+1) (y-1) + node x (y-1) + node (x-1) (y-1)

每当我运行这个我得到：

"*异常：堆栈溢出”？

我相信您的问题比示例代码所示的要复杂一些。首先，让我们明确一些定义：

Let pathCount x y是结束于 (x, y) 的路径数。我们有

pathCount :: Int -> Int -> Integer
pathCount x y
  | y == 0 = if x == 0 then 1 else 0
  | otherwise = sum [ pathCount (x + d) (y - 1) | d <- [-1..1]]

现在让我们pathSum x y是以 (x, y) 结尾的所有路径的总和。我们有：

pathSum :: Int -> Int -> Integer
pathSum x y
  | y == 0 = if x == 0 then 1 else 0
  | otherwise = sum [ pathSum (x + d) (y - 1) + node x y * pathCount (x + d) (y - 1)
                     | d <- [-1..1] ]

有了这个助手，我们终于可以定义node x y适当地：

node :: Int -> Int -> Integer
node x y
  | y == 0 = if x == 0 then 1 else 0
  | otherwise = sum [ pathSum (x + d) (y - 1) | d <- [-1..1]]

该算法目前的形式是指数时间。但是我们可以添加记忆化使加法次数成二次方。这memoizeHackage 上的软件包让这一切变得非常简单。完整示例：

import Control.Monad
import Data.List (intercalate)
import Data.Function.Memoize (memoize2)

node' :: Int -> Int -> Integer
node' x y
  | y == 0 = if x == 0 then 1 else 0
  | otherwise = sum [ pathSum (x + d) (y - 1) | d <- [-1..1]]
node = memoize2 node'

pathCount' :: Int -> Int -> Integer
pathCount' x y
  | y == 0 = if x == 0 then 1 else 0
  | otherwise = sum [ pathCount (x + d) (y - 1) | d <- [-1..1]]
pathCount = memoize2 pathCount'

pathSum' :: Int -> Int -> Integer
pathSum' x y
  | y == 0 = if x == 0 then 1 else 0
  | otherwise = sum [ pathSum (x + d) (y - 1) + node x y * pathCount (x + d) (y - 1)
                     | d <- [-1..1] ]
pathSum = memoize2 pathSum'

main =
  forM_ [0..n] $ \y ->
     putStrLn $ intercalate " " $ map (show . flip node y) [-n..n]
  where n = 5

Output:

0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0
0 0 0 2 4 6 4 2 0 0 0
0 0 4 16 40 48 40 16 4 0 0
0 8 72 352 728 944 728 352 72 8 0
16 376 4248 16608 35128 43632 35128 16608 4248 376 16

正如您所看到的算法，数字的大小很快就会失控。所以运行时间是notO(n^2)，而算术运算次数为。