Problem 67 「最大経路の和 その2」 †

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23

100列の三角形を含んでいる15Kのテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけてください.

注：これは, Problem 18のずっと難しいバージョンです.
全部で299 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません！
あなたが毎秒1兆本の(1012)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう.
解決するための効率的なアルゴリズムがあります. ;o)

解法

一段ずつの動的計画法で解けます。

max(X1,X2,X2):-X1<X2,!.
max(X1,_,X1):-!.

next_calc([X],[Y],[Z]):-
      !,
      Z is X+Y.
next_calc([X1,X2|Rest],[Y|Rest1],[Z|Result]):-
      !,
      max(X1,X2,X3),
      Z is X3+Y,
      next_calc([X2|Rest],Rest1,Result).

calc([],List):-
      !,
      msort(List,List1),
      reverse(List1,[Ans|_]),
      write(Ans).

calc([NowRow|Datas],OldRow):-
      !,
      [NowLeft|NowRow1]=NowRow,
      next_calc(OldRow,NowRow1,NowRow2),
      [OldLeft|_]=OldRow,
      NowLeft1 is NowLeft+OldLeft,
      calc(Datas,[NowLeft1|NowRow2]).

main67:-
      open('pe67.txt',read,IS),
      read_term(IS,[Top|Datas],[]),
      close(IS),
      calc(Datas,Top).