# Project Euler: Problem 18 – Maximum path sum I

#### Problem 18:

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)

#### Idea:

Before I noticed the note at the bottom, I was going to use a brute-force method. However, seeing recurring themes / patters in these problems (i.e. especially with prime numbers), and given the fact that this same problem occurs again in Problem 67, I figured might as well do it right the first time.

Thinking back to Problem 14, I realized I could make it more efficient by only computing the Collatz chain for a given number once, storing it, then just retrieving it whenever another number produced a chain that landed on that number. I figured I’d try a similar approach with this problem. However, I couldn’t do it from a top down approach (as that would be relatively equivalent to a brute-force method).

I decided to start from the base and work my way up, keeping track of the maximal path to the bottom for each node as I went. By the time I get to the top, I’ll have the maximal path to the bottom at that particular node (the starting node), which itself is the answer. I chose to use a custom data type to store not only the path length, but also a reference to the next node along the path to help me visualize the path from top to bottom, just in case I needed something like that for future problems.

```int answer = -1;

//In the form of a right triangle, max element is [i][i] per row

//SumTreePath is a helper class that stores the current value, the total sum
//thus far, and the reference to the next SumTreePath node
Euler.SumTreePath path = treePath(tree,true);

//==========================================
private static Euler.SumTreePath treePath(int[][] tree, boolean maximal) {
Euler.SumTreePath[][] sumTree;

boolean MAXIMAL = maximal;
sumTree = new Euler.SumTreePath[tree.length][];

//initialize last row of sums
sumTree[tree.length-1] =
new Euler.SumTreePath[tree[tree.length-1].length];
for(int i = 0; i < tree[tree.length-1].length; i++) {
sumTree[tree.length-1][i] =
new Euler.SumTreePath(tree[tree.length-1][i],tree[tree.length-1][i], 0);
}

for(int i = tree.length-2; i >= 0; i--) {
sumTree[i] = new Euler.SumTreePath[tree[i].length];
for(int j = 0; j < tree[i].length; j++) {
//calculate cumulative sum of left choice
int sum1 = tree[i][j] + sumTree[i+1][j].getSum();
//calculate cumulative sum of right choice
int sum2 = tree[i][j] + sumTree[i+1][j+1].getSum();

Euler.SumTreePath sumTreeValue =
new Euler.SumTreePath(tree[i][j],sum1,tree[i+1][j]);
if(sum2 > sum1 && MAXIMAL) {
sumTreeValue =
new Euler.SumTreePath(tree[i][j],sum2,tree[i+1][j+1]);
}

sumTree[i][j] = sumTreeValue;
}
}

//Return root node (current value, current sum, reference to next node)
return sumTree;
}```