## Project euler problem 18 and 67

Project euler problem 67 and 16 both are almost same. The only difference is that for the first problem the input is very small and for the 67th problem it is large. This problem is one another **classic** example of **Dynamic programming.**

**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

**Solution:**

Just by looking at the problem we can quickly discern that it has optimal sub structure and overlapping sub problems. This gives an idea that we can use dynamic programming methodology.

Here is my code in Python.

apyr=[] def pyr(): with open("pyramid.txt", "r")as out: for i in out: apyr.append(i.split()) for i in range(len(apyr) - 2, -1, -1): for j in range(len(apyr[i])): apyr[i][j] = str(int(apyr[i][j]) + max(int(apyr[i + 1][j]), int(apyr[i + 1][j + 1]))) print apyr[0][0] pyr()

Answer for problem 16: 1074

Answer for problem 67: 7273

real 0m0.195s

user 0m0.046s

sys 0m0.140s