title: Dynamic programming in the functional paradigm
body: <p>I'm looking at <a href="http://projecteuler.net/index.php?section=problems&amp;id=31" rel="noreferrer">Problem thirty one</a> on Project Euler, which asks, how many different ways are there of making £2 using any number of coins of 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).</p>
  <p>There are recursive solutions, such as this one in Scala (credit to Pavel Fatin)</p>
  <pre><code>def f(ms: List[Int], n: Int): Int = ms match {
    case h :: t =&gt;
      if (h &gt; n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
    case _ =&gt; 0
  } 
  val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)
  </code></pre>
  <p>and although it runs fast enough, it's relatively inefficient, calling the <code>f</code> function around 5.6 million times.</p>
  <p>I saw someone else's solution in Java which was programmed dynamically (credit to wizeman from Portugal)</p>
  <pre><code>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 &lt;= TOTAL; j++) {
              ways[j] += ways[j - coin];
          }
      }
  
      System.out.println(&quot;Result: &quot; + ways[TOTAL]);
  }
  </code></pre>
  <p>This is much more efficient and passes the inner loop only 1220 times.</p>
  <p>While I could obviously translate this more or less verbatim into Scala using <code>Array</code> objects, is there an idiomatic functional way to do this using immutable data structures, preferably with similar conciseness and performance?</p>
  <p>I have tried and become stuck trying to recursively update a <code>List</code> before deciding I'm probably just approaching it the wrong way.</p>