Project Euler Problem 18
方法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))