Help us understand the problem. What is going on with this article?

Project Euler 67「最大経路の和 その2」

More than 1 year has passed since last update.

Problem64~66は分からん過ぎて諦めた。

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

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

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

100列の三角形を含んでいる15Kのテキストファイル triangle.txt の上から下まで最大合計を見つけよ.

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

def hoge(path):
    numbers = open(path).read().strip().split('\n')
    numbers = [ x.split() for x in numbers ]
    numbers = [ [ int(m) for m in n ] for n in numbers ]
    numbers.reverse()
    for i, row in enumerate(numbers):
        if i + 1 == len(numbers):
            break
        row2 = numbers[i+1]
        numbers[i+1] = [ n + max(row[j:j+2]) for j, n in enumerate(row2) ]
    return numbers[-1][0]

print(hoge('p067_triangle.txt'))

Problem 18で書いたコードをほぼそのまんま流用しただけ。

三角形の下から上へ処理していくイメージ。
i行目(row)とi+1行目(row2)を取得し、i+1行目の各値に対して隣接するi行目の値の大きい方を加算していくと、最終的に頂点の値が最大値になる寸法。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away