### Problem

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

### Analysis

The brute force approach to this problem would involve tracing every path and computing the maximum path cost. The time complexity of this algorithm is **O(2 ^{n})** where

**n**is the number of rows in the triangle (minus the first). For our triangle of 15 rows, 2

^{14}= 16384 paths to compute. This is acceptable, but Problem #67 poses a much larger version of the same problem with a 100 row triangle! Testing 2

^{99}paths is an intractable problem so a more efficient algorithm is required.

That efficient algorithm, or at least one of them, is to use the dynamic programming approach. By splitting up the triangle into small sub-triangles, and working from the bottom-up, we can compute the maximum path in a single pass. For each cell in the triangle we find the max of the two cells below it and add that to the cell value. This algorithm has time complexity **O(n)**, where n is the number of cells, a vast improvement over brute force!

### Code

Here is my Python solution. I represent the triangle as a list of lists, each inner list is a row. Starting at the second last row and moving upwards, for each cell in this structure I compute `cell(i,j) += max(cell(i+1,j), cell(i+1,j+1))`

. The cell at the top of the triangle will contain the maximum path cost.

```
import time
# a list to represent the triangle
triangle = []
# read the data file
data_file = open("triangle.txt", "r")
# for each line in the data file, append a row (list) to the triangle
for line in data_file:
row = [int(i) for i in line.split(" ")] # convert the line to a list
triangle.append(row)
# time.clock() measures cpu time not actual time
start_time = time.clock()
# for each cell in the triangle, add the max of the cells below-left and
# below-right. the cell at the top will contain the greatest sum from bottom
# to top
for i in range(len(triangle)-2,-1,-1):
for j in range(i+1):
triangle[i][j] += max([triangle[i+1][j],triangle[i+1][j+1]])
elapsed_time = time.clock() - start_time
print "maximum path cost: %d" % (triangle[0][0])
print "time elapsed: %f ms" % (elapsed_time * 1000)
```

### Results

I've spoilered the answer to each problem in case you want to find it for yourself.For the 15 row triangle in Problem #18:

`maximum path cost: 1074`

`time elapsed: 0.198637 ms`

and the 100 row triangle in Problem #67:

`maximum path cost: 7273`

`time elapsed: 8.080979 ms`