プロジェクトオイラー18

プロジェクトオイラーの問題18をPythonで解きました。

projecteuler.net

全てのルートを探索し、その中から目当てのものを見つけるのが最も考え方としてシンプルだと思うのですが、それだと、15!通り調べなければならないため、時間がかかります。（たぶん）そこで、

動的計画法 - Wikipedia

を用いてコードを書きました。

import time
data = [input().split(' ') for i in range(15)] #a given data
start = time.time()
j = 14
while j > 0:
    for i in range(j):
        data[j-1][i] = int(data[j-1][i]) +  max(int(data[j][i]), int(data[j][i+1]))
    j += -1
print(data[0][0])
print(time.time() - start)

入れるデータは、

です。
今回から実行するのにかかった時間も計算してみました。