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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2067
Problem 67 「最大経路の和 その2」 †
三角形に並んだ数字を上から下へ和を求めながら進むとき和が最大になる経路の値を答えよ。


解法
1行一リストとして素直にDPです。


read_data(X):-
	see('pe67.txt'),
	read(X),
	seen.

max(A,B,A):-A>B,!.
max(_,B,B):-!.

calc_row([X],[Y],[Z]):-
	!,
	Z is X+Y.

 
calc_row([X,Y|Rest],[Z|Rest1],[Z1|Result]):-
	max(X,Y,Add),
	Z1 is Z+Add,
	calc_row([Y|Rest],Rest1,Result).

calc(DP,[]):-
	!,
 	sort(DP,DP1),
	reverse(DP1,[Ans|_]),
	write(Ans).

calc(DP,[RowA|Rest]):-
	[L|RowB]=RowA,
 	calc_row(DP,RowB,DP1),
	[L2|_]=DP,
	L3 is L2+L,
	calc([L3|DP1],Rest).

main:-
	read_data([Top|Rest]),
	calc(Top,Rest).
最終更新:2014年12月12日 13:08