LCS -- naiver Algorithmus (exponentiell)

-- | Länge einer längsten gemeinsamen Teilfolge
lcs :: Eq a => [a] -> [a] -> Int
lcs [] ys = 0
lcs xs [] = 0
lcs (x : xs) (y : ys) =
  maximum 
    [ if x == y then 1 + lcs xs ys
                else     lcs xs ys
    , lcs      xs  (y : ys)
    , lcs (x : xs)      ys 
    ]

top-down: sehr viele rekursive Aufrufe ...

aber nicht viele verschiedene ...

Optimierung durch bottom-up-Reihenfolge!