067 : 最大経路の和 その2(**)

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

   3
  7 4
 2 4 6
8 5 9 3

(3,7,4,9を強調したい)

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

100行からなる三角形を持つ15Kのテキストファイル triangle.txt （右クリックして、『名前をつけてリンク先を保存』）の上から下までの最大合計を見つけよ。

注：これは Problem 18のずっと難しいバージョンである。 全部で$2^{99}$通りの組み合わせがあるので、この問題を解くのに全ての経路を試すことは不可能である！ 毎秒1兆($10^{12}$)本の経路を調べることができたとしても、全てを調べるには200億年以上かかるだろう。 この問題を解く効率的なアルゴリズムがある ;o)