Решение задачи №144 от UniLecs (Super Mario), Haskell

Main.hs

import Data.List (scanl', tails, intercalate, sort)
import Data.Monoid ((<>), Sum(..))
import Data.Function (on)

accumulated :: Monoid a => [a] -> [a]
accumulated = scanl' (<>) mempty

accumSums :: Num a => [a] -> [a]
accumSums = map getSum . accumulated . map Sum

accumConcat :: [[a]] -> [[a]]
accumConcat = accumulated

onSegs f k = go
  where
    go = map (f . take k) . tails

sumSegs = onSegs sum
concatSegs = onSegs concat

-- | Возвращает список количеств способов добраться 
-- до соответствующей ступеньки при условии, что
-- можно прыгать через k ступенек.
-- Нулевой элемент — 1, т. к. преодолеть лестницу без ступенек можно всегда.
-- Первые k элементов после нулевого являются степенями двойки.
-- Далее элементы равны сумме k предыдущих.
marioWaysCount :: Int -> [Integer]
marioWaysCount k = 1 : list
  where
    list = prefix ++ sumSegs k list
    prefix = take k $ iterate (*2) 1

type Path = [Int]

-- | Возвращает список путей до n-ой ступеньки при максимальной длине прыжка k.
-- Для нулевой ступеньки путь тривиален. Для всех остальных берём пути
-- до k предыдущих ступенек, добавляем n-ую в конце и объединяем результаты.
marioWays' :: Int -> Int -> [Path]
marioWays' k n
    | n == 0 = [[0]]
    | otherwise = concatMap (map (++ [n]) . marioWays' k) . take k . takeWhile (>=0) $ [(n - 1), (n - 2)..]

-- | Возвращает список путей до ступенек при максимальной длине прыжка k.
-- Мемоизирует промежуточные результаты (в виде возращаемого списка), поэтому
-- работает заметно быстрее marioWays'.
marioWays :: Int -> [[Path]]
marioWays k = map (map reverse) $ [[0]] : (map (++ [0]) <$> list)
  where
    list = prefix ++ zipWith appendToPaths [k+1..] (concatSegs k list)
    prefix = take k $ zipWith (\i paths -> [i] : appendToPaths i paths) [1..] (accumConcat prefix)
    appendToPaths i paths = map (i:) paths

printLines :: Show a => [a] -> IO ()
printLines = putStrLn . unlines . map show

main = do
    -- Выводим число путей до ступенек от нулевой до сотой
    -- при длине прыжка 100 (максимальные значения по условию задачи)
    printLines . (take 100) $ marioWaysCount 100

    -- Выводим все пути до 10 ступеньки при максимальной длине прыжка 3
    putStrLn . unlines . map (intercalate " -> " . map show) . sort . (!! 10) $ marioWays 3

    -- Сравниваем первые 10 результатов, полученных marioWays' и marioWays.
    -- Т. к. методы разные, сортируем списки путей перед сравнением.
    -- Должен распечатать список из одних `True`.
    print . take 10 . zipWith ((==) `on` sort) (marioWays 3) $ map (marioWays' 3) [0..]

В математике существует концепция моноида. Это тройка из: некоего множества, двухместной операции на элементах множества, которая ассоциативна и замкнута относительно множества, и некоего выделенного элемента множества, который является для этой операции нейтральным справа и слева. Это идея выражена в классе типов Monoid. В терминах этого класса типов операция — это <>, а нейтральный элемент — mempty. Функция accumulated принимает на вход список элементов и возвращает результаты последовательного объединения первых 0, 1, 2... элементов списка.

Для списков <> = ++ (конкатенация), а нейтральный элемент — [] (пустой список). Поэтому accumConcat возвращает пустой список, первый список из аргумента, объединение первого и второго списков из аргумента и т. д.

onSegs f k возвращает функцию, которая выделяет из входного (предположительно бесконечного) списка перекрывающиеся отрезки длины k, и применяет к каждому из них функцию f.

Если ступенек нет (n = 0), то количество путей равно 1. Иначе количество способов добраться до i-ой ступеньки равно сумме k предшествующих элементов. На отрезке n <= k количество способов добраться до n-ой ступеньки равно:
1, если n = 1,
2^{n - 1}, если n ≠ 1.
Это несложно доказать методом математической индукции.