Problem 15

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

格子の端から端までの経路の数

3つ目まで机上で問いたら分かった。下の表のように格子点 (x,y)の経路数は
格子点 (x-1, y) の経路数 + 格子点 (x, y-1)の経路数なのか。

1	1	1	1
1	2	3	4
1	3	6	10
1	4	10	20

この表をつくって、20行、20列目にアクセスすればOK。

main = print $ numOfGridRoute !! n !! n
    where n = 20

numOfGridRoute = scanl f [1,1..] [1,1..]
    where f xs y = (scanl (+) y $ tail xs)

対称だからもう少し最適化できそう。

1	-	-	-
1	2	-	-
1	3	6	-
1	4	10	20

main = print $ numOfGridRoute !! n !! n
    where n = 20

numOfGridRoute' = scanl f [1] [1,1..]
    where f xs y = ns ++ [(last ns) * 2]
              where ns = (scanl (+) y $ tail xs)

20くらいだと性能差がよくわからんけど、1000くらいにするとわかる.
ns 作ってから、さらに一番後ろまで行って2倍してそれをまた一番後ろまで行って。。なんとかならんのか。