我正在解决一个递归问题,使用haskell语言,虽然我已经得到了解决方案,但我想缓存子问题的输出结果,因为存在重叠子问题的属性。
问题是:给定一个n*m尺寸的网格和一个整数k,从(1,1)出发到达(n,m),最多改变k次方向,有多少种方式?
以下是没有记忆化的代码。
问题是:给定一个n*m尺寸的网格和一个整数k,从(1,1)出发到达(n,m),最多改变k次方向,有多少种方式?
以下是没有记忆化的代码。
paths :: Int -> Int -> Int -> Int -> Int -> Int -> Integer
paths i j n m k dir
| i > n || j > m || k < 0 = 0
| i == n && j == m = 1
| dir == 0 = paths (i+1) j n m k 1 + paths i (j+1) n m k 2 -- is in grid (1,1)
| dir == 1 = paths (i+1) j n m k 1 + paths i (j+1) n m (k-1) 2 -- down was the direction took to reach here
| dir == 2 = paths (i+1) j n m (k-1) 1 + paths i (j+1) n m k 2 -- right was the direction took to reach here
| otherwise = -1
这里的依赖变量是i
,j
,k
和dir
。在像C ++ / Java这样的语言中,可以使用4-d DP数组(dp [n] [m] [k] [3]
),但是在Haskell中,我找不到实现这种方式的方法。