Project Euler Problem 18

Python

方法1

下の行から処理する。
隣り合う2つの数の内、大きいものを選んで、
その数を上の数に足して、上の数を上書きする。

3
7 4
2 4 6
8 5 9 3

3
7 4
10 13 15

3
20 19

23

f = open('data', 'r')

data_list = []
for line in f:
    data_list.append(list(map(int, line.split())))

f.close()

data_list.reverse()

for i in range(len(data_list) - 1):
    for j in range(len(data_list[i]) - 1):
        if data_list[i][j] > data_list[i][j + 1]:
            data_list[i + 1][j] += data_list[i][j]
        else:
            data_list[i + 1][j] += data_list[i][j + 1]

print(data_list[-1][0])
方法2

再帰を使う
a = 頂点の左下を頂点とする最大値
b = 頂点の右下を頂点とする最大値
最大値は、aとbの内大きいものと頂点の数を足したものである。

def max_path_sum(idx1, idx2):
    if idx1 == len(data_list) - 1:
        return data_list[idx1][idx2]
    else:
        left_child = max_path_sum(idx1 + 1, idx2)
        right_child = max_path_sum(idx1 + 1, idx2 + 1)
        if left_child > right_child:
            return data_list[idx1][idx2] + left_child
        else:
            return data_list[idx1][idx2] + right_child

f = open('data', 'r')

data_list = []
for line in f:
    data_list.append(list(map(int, line.split())))

f.close()

print(max_path_sum(0, 0))