最长公共子序列(Haskell)

Question

我已经在这个问题上挣扎了一段时间。我正在解决Haskell中最长的公共子序列问题作为学习练习。

我有一个传递给两个Int i和j的函数f1，以及一个函数f2。f1构建了一个二维列表，以便列表中的(i，j)位置等于f2 i j。

现在，我尝试编写一个名为lcs的函数，该函数接受两个字符串s1和s2，并使用f1查找最长的公共子序列进行记忆。

我不太确定如何设置它。有什么想法吗？

代码：

f1 :: Int -> Int -> (Int -> Int -> a) -> [[a]]

f2 :: Int -> Int -> a

lcs:: String -> String -> Int

Answer 1

我假设f1的Int参数是某种界限？请记住，使用列表的好处是不需要指定界限(因为懒惰)，但它会降低访问时间。

这个函数应该做你想让f1做的事情(记住一个给定的函数)：

memo :: (Int -> Int -> a) -> (Int -> Int -> a)
memo f = index where
  index x y = (m !! x) !! y
  m         = [[f x y|y <- [0..]]|x <- [0..]]

-- memoized version of f2
f2' = memo f2