We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Memoization and DP
  4. Different Ways
  5. Discussions

Different Ways

  • mykhail0
     + 0 comments

    Simple bottom up DP solution in Haskell using arrays:

    import Control.Monad (replicateM_)
import Data.Array

main :: IO ()
main = readLn >>= flip replicateM_ (do
  l <- getLine
  let [n, k] = fmap read $ words l
  print $ combs ! n ! k)

combs :: Array Int (Array Int Int)
combs = listArray (0, 1000) $ rowToArray <$> combinations
  where rowToArray l = listArray (0, length l - 1) l

combinations :: [[Int]]
combinations = [1] : (nextRow <$> combinations)
  where
    nextRow l@(_:t) = 1 : (zipWith f l t) ++ [1]
    f x y = (x + y) `mod` (10^8 + 7)