プロジェクトオイラー問15

Problem 15 「格子経路」 †

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

では, 20×20 のマス目ではいくつのルートがあるか.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015

解法

40！/20!*20！が一番正しいですが。

動的計画法で素朴にもやってみました。

last([X],X):-!.
last([_|Xs],Result):-last(Xs,Result).
roopC(_,[],[]):-!.
roopC(Sum,[X|Xs],[Sum1|Ys]):-
      Sum1 is Sum+X,
      roopC(Sum1,Xs,Ys).


roopR(21,List):-!,last(List,Ans),write(Ans).
roopR(R,[Top|List]):-
      !,
      roopC(Top,List,List1),
      R1 is R+1,
      roopR(R1,[1|List1]).
seed(1):-!,between(1,21,_).

main15:-
      findall(E,seed(E),Seed),
      roopR(1,Seed).