This is what I am currently working on:
I don’t have the solution yet, so this blog post will contain some thoughts that hopefully will at least lead me in the right direction.
Always pick the highest number?
My first idea was to always pick the highest adjacent number. This is what’s done in the given example: 3 + 7 + 4 + 9.
This would lead to 75 + 95 + 47 + 87 + 82 + 75 + 73 + 28 + 83 + 47 + 43 + 73 + 91 + 67 + 98 = 1064. Unfortunately this is not the correct solution.
Therefore going for the highest number is not the correct strategy.
Is it a tree?
This looks like a tree. But I have to be careful.
This is not the kind of tree I am looking for, as I could never reach from node “4” to the adjacent node with the same value:
What I need is a tree that looks like the following:
So how to do I create such a structure programmatically?
The problem shows a root node plus 14 additional node levels. This might result in heavy typing which I want to avoid.
Work from top or bottom?
Once I have a tree, how do I process it? Looks like a call for recursion? Top-down? Bottom-up?
I know that 1064 is not the correct solution. Therefore the solution must be a larger number. Also it cannot be more than 1313. Most likely the solution is closer to 1064.
2 thoughts on “Project Euler – Maximum path sum (Part 1)”