Euler project #18 approach

Question

I am looking into an Euler project. Specifically #18.
To sum up, the idea is to find the max path from a triangle:

   3   7 4  2 4 6   8 5 9 3 

3 + 7 + 4 + 9 = 23.

Reading for this, most people indicate that this is solved correctly by working bottom to top instead of using an algorithm that works "greedy" from top to bottom.

I can understand that starting from top and going down selecting the max you find is "shortsighted" and may not be the overall max.

But why is the approach of going from bottom to top any better?
It seems to me it suffers from the same problem.

For example in the triangle in the example we would get (starting from bottom):
9+6+4+3=22 < 23

So why start from bottom-up?

Answer 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.