Project Euler 31

http://projecteuler.net/index.php?section=problems&id=31

素直に書くと次のようになるでしょうか。

let coins = [ 1; 2; 5; 10; 20; 50; 100; 200 ]

// nポンドをm番目までのコインを使って何通りの表し方があるか
let rec num_ways n m =
   if n = 0 || m = 0 then 1
   else Seq.sum (Seq.map (fun x -> num_ways x (m - 1))
                (Seq.takeWhile (fun x -> x >= 0)
                (Seq.map (fun k -> n - coins.[m] * k)
                (seq { 0..n }))))

printfn "%d" (num_ways 200 7)

このコードで瞬間的に解が得られます。しかし、このコードは同じ計算を何度もしています。こういうときはメモ化を使うのが定番です。
Mapは次のように使います。

let m = Map.empty
let m2 = m.Add (1, 2)
let m3 = m2.Add (3, 4)
printfn "%d" (m3.Item 1)         // 2
printfn "%b" (m3.ContainsKey 3)  // true

Addすると新たなMapができます。
再帰的な方法もありますが、ここでは使いにくいので、mutableにします。

let mutable m = Map.empty
m <- m.Add (1, 2)
m <- m.Add (3, 4)
printfn "%d" (m.Item 1)
printfn "%b" (m.ContainsKey 3)

これでメモ化できます。200ポンドを1000ポンドにすると、最初のコードはなかなか返ってきませんでしたが、メモ化を使うとすぐに返ってきました。

let coins = [ 1; 2; 5; 10; 20; 50; 100; 200 ]
let mutable dic = Map.empty

let rec num_ways n m =
    let t = (n, m)
    if dic.ContainsKey t then
        dic.Item t
    else
       if n = 0 || m = 0 then 1
       else
        let v = Seq.sum (Seq.map (fun x -> num_ways x (m - 1))
                             (Seq.takeWhile (fun x -> x >= 0)
                             (Seq.map (fun k -> n - coins.[m] * k)
                             (seq { 0..n }))))
          dic <- dic.Add (t, v)
          v

printfn "%d" (num_ways 1000 7)