Project Euler その14

Problem18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

訳

以下の三角形の頂点からスタートし、下の列の隣接する数字へ移動していくと、上から下までの最も大きな総和は23である。
3
7 4
2 4 6
8 5 9 3
すなわち、3 + 7 + 4 + 9 = 23である。

以下の三角形の上から下までの最大の和を求めよ。
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

コード

D = 15

T ="75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
T = map(int, T.split(" "))
N = [0]*len(T)
j = D - 1
k = 0

for i in range(len(T)-D,len(T)):
    N[i] = T[i]

for i in range(0,len(T)-D)[::-1]:
    N[i] = max([N[i+j],N[i+j+1]])+T[i]
    k += 1
    if k == j:
        k = 0
        j -= 1

print N[0]

上からたどると重いので下からたどっていく。
ある要素の左下・右下の数字のうち大きな方をその要素に足し合わせていく。
これを下から繰り返し行えば最大値は容易に求まる。