Динамическое программирование в функциональной парадигме

Я смотрю на Задачу тридцать один в Project Euler, которая спрашивает, сколько существует различных способов заработать 2 фунта стерлингов, используя любое количество монет 1p, 2p, 5p, 10 пенсов, 20 пенсов, 50 пенсов, 1 фунт стерлингов (100 пенсов) и 2 фунта стерлингов (200 пенсов).

Существуют рекурсивные решения, такие как это в Scala (кредит Павел Фатин)

def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
  case _ => 0
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)

, и хотя оно работает достаточно быстро, оно относительно неэффективно, вызывая функцию f около 5,6 миллиона раз.

Я видел другое решение на Java, которое было запрограммировано динамически (заслуга wizeman из Португалии)

final static int TOTAL = 200;

public static void main(String[] args) {
    int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
    int[] ways = new int[TOTAL + 1];
    ways[0] = 1;

    for (int coin : coins) {
        for (int j = coin; j <= TOTAL; j++) {
            ways[j] += ways[j - coin];
        }
    }

    System.out.println("Result: " + ways[TOTAL]);
}

Это гораздо более эффективно и проходит внутреннюю цикл только 1220 раз.

Хотя я, очевидно, мог бы более или менее дословно перевести это на Scala, используя объекты Array , существует ли идиоматический функциональный способ сделать это с использованием неизменяемых структур данных, желательно с такой же краткостью и производительностью ?

Я попытался и застрял, пытаясь рекурсивно обновить список , прежде чем решить, что я очевидно, просто приближаюсь к нему неправильно.