Problem 67 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 67 へ行く。
  • 1 (2016-07-17 (日) 16:00:29)

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

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

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

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

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