Euler project #18 approach

Solution 1:

It's something called dynamic programming.

You have such triangle:

   3
  7 4
 2 4 6  
8 5 9 3

When you move from the bottom to the top, you can calculate the best choices on last iteration. In this case you take the last row 8 5 9 3 and maximize sum in addition to previous line.

Iteration 1: Assume that you are on last-1 step.

You have line 2 4 6, let's iterate on it.

From 2, you can go to either 8 or 5, so 8 is better (maximize your result from 2) so you calculate first sum 8 + 2 = 10.

From 4, you can go to either 5 or 9, so 9 is better (maximize your result from 4) so you calculate second sum 9 + 4 = 13.

From 6, you can go to either 9 or 3, so 9 is better again (maximize your result from 6) so you calculate third sum 9 + 6 = 15.

This is the end of first iteration and you got the line of sums 10 13 15.

Now you've got triangle of lower dimension:

    3
  7  4
10 13 15  

Now go on until you get one value, which is exactly 23.

Solution 2:

The difference is not between top-down and bottom-up. The difference is between greedy and 'frontier' methods.

A greedy algorithm won't necessarily help you, because you can't recover if the best part of the tree gets out of reach. For example: a greedy algorithm would choose the path 1-3 from top to bottom. It would miss the 9 entirely.

    1
   2 3
  9 1 1

In order to find the true maximum, you'd have to essentially traverse nearly all paths.

The bottom-up approach, as it is described, doesn't have this problem. It examines at most n*(n-1) paths: 2 for each element. However, calling it the 'bottom-up' approach is misleading.

Why? Because there is a top-down approach that is equivalent. The essence is that you have a kind of 'frontier' with best results for all trees behind the frontier. Whether you move the frontier up or down is secondary. For the top-down approach in the above example, you calculate for each row the sum of each element and the maximum of the two best totals above it:

     1
    3 4
  12 5 5

In the bottom-up approach, you calculate for each row the sum of each element and the maximum of the two best totals below it. In reverse order:

  9  1 1
   11 4
    12

There is about equal work in both these top-down and bottom-up approaches.

Solution 3:

Using your example, the "bottom up" way to approach it is:

Examining the bottom row, the most you can get from each element is

8,5,9,3

Examining the next-to-bottom row, the most you can get from each element is (depending on whether you go left or right from it):

2+max(8,5),4+max(5,9),6+max(9,3) = 10,13,15

So this is great; we've eliminated 2 rows by squishing them together to replace them with one row, reducing the problem to

     3
   7   4
10  13  15

Obviously we can just keep repeating this. Examining the next row up, the most you can get from each element is

7+max(10,13),4+max(13,15) = 20,19

And so from the top, the most you can get is

3+max(20,19) = 23

QED.