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
NOTE: As there are only \(16384\) routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
Politely ignoring the Gamzee emoticon at the end, the problem's note is correct: there's a shortcut available, and for the sake of learning it's advisable to not take it, so I won't.
This problem exhibits optimal substructure: an optimal solution can be constructed from joining the optimal solutions to its subproblems. If we want to know the maximal path that ends at a certain number, we know the penultimate number will be one of the two numbers just above it, and the rest of the route will be the maximal path to that number. Denote \(a_{i,j}\) as the \(j\)-th element of the \(i\)-th row, and denote \(c_{i,j}\) as the maximal path to that element; then \(c_{i,j} = a_{i,j} + \max(c_{i-1,j-1}, c_{i-1,j})\), with boundary conditions \(c_{i,0} = c_{i,i+1} = 0\) for all \(i\). If we keep track of the values of \(c_{i,j}\) after analyzing row \(i\), we can find the values for the next row in linear time. The answer is just the maximum of \(c_{15,j}\) over \(j\).
def p18():
tri = """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"""
c = [0, 0]
for row in tri.split('\n'):
a = list(map(int, row.split(' ')))
c = [0] + [a[j] + max(c[j:j+2]) for j in range(len(a))] + [0]
return max(c)