algorithm for project euler problem no 18

Question

Problem number 18 from Project Euler's site is as follows:

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)

The formulation of this problems does not make clear if

• the "Traversor" is greedy, meaning that he always choosed the child with be higher value
• the maximum of every single walkthrough is asked

The NOTE says, that it is possible to solve this problem by trying every route. This means to me, that is is also possible without!

This leads to my actual question: Assumed that not the greedy one is the max, is there any algorithm that finds the max walkthrough value without trying every route and that doesn't act like the greedy algorithm?

I implemented an algorithm in Java, putting the values first in a node structure, then applying the greedy algorithm. The result, however, is cosidered as wrong by Project Euler.

sum = 0;

void findWay(Node node){
    sum += node.value;
    if(node.nodeLeft != null && node.nodeRight != null){
            if(node.nodeLeft.value > node.nodeRight.value){
                findWay(node.nodeLeft);
            }else{
                findWay(node.nodeRight);
            }
        }
}

Answer 1

Spoiler alert: This answer leads you to a solution, but does not implement it

---

Using WuHoUnited's example, modified for uniqueness:

   9
  7 0
 2 4 6
8 5 1 3

Ask yourself this: If you found yourself at 2, would you ever take 8 instead of 5, knowing they are the leaf nodes of the tree? Similarly, If you found yourself at 6, would you ever take 3 instead of 1, knowing those are the leaf nodes of the tree?

Certainly not. We can now reduce the tree, knowing what decision we'd take at the penultimate branch (regardless of how we got there):

   9
  7 0
10 9 9

I think you see where this is going.

Answer 2

As somebody who has solved the problem I can tell you that the greedy algorithm is NOT what they are looking.

It is looking for the maximum value of all possible routes.

example

   3
  7 4
 2 4 6
8 5 1 3

3+7+4+5 = 19 <- greedy
3+7+2+8 = 20 <- not greedy

So the answer should be 20

Answer 3

Dijkstra's algorithm for shortest paths (turn all edges negative).

Answer 4

Greedy approach is definitely not the approach you should consider for this problem. Think of a solution that exhaustively checks all possible routes and find the maximum. Then optimize it using Dynamic programming.