【Project Euler】Problem 67: 経路の合計の最大値 （その２）

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 67. 経路の合計の最大値 （その２）

原文 Problem 67: Maximum path sum II

問題の要約：triangle.txtの100行のピラミッド型の数の上から下まで数字をたどった経路の合計の最大値を求めよ

これはProblem 18: 経路の合計の最大値 （その１）の拡大版と言えます。アルゴリズムはProblem 18と同じで良いので。データを同様な配列に入れればプロクラムにはそのままでOKです。

for y in range(len(triarr)-2,-1,-1):
  for x in range(y+1):
    triarr[y][x] += max(triarr[y+1][x],triarr[y+1][x+1])
print(f"Answer: {triarr[0][0]}")

ファイルから読んで配列に入れるプロクラム。

# show upload dialog
from google.colab import files
uploaded = files.upload()
#---- read numbers from file
f = open("p067_triangle.txt")
triNums = f.readlines()
f.close()
triarr = [list(map(int,row.split())) for row in triNums]
print(triarr[:20])

（開発環境：Google Colab）