The other day, I visited Project Euler, and solved a few problems. Two of which involved a pyramids. You are asked to find the way from the top to bottom which gives the highest possible sum. In this post I explain how you can solve this super efficiently.

Let's start out with a small pyramid to make sure we understand the concept.

Try to work out the best path. We start at the top, with 24, and choose the higher number of the two below (57). Then we check which one's the higher one of the two below that one (72). So it becomes: 24 + 57 + 72 = 153. Easy. How about this one?

This one isn't quite as straight-forward. You can still figure it out, relatively easily, but this is still a very small pyramid. Now let's see if we can come up with a clever way to solve this Great Pyramid of ... numbers:

As you can see, I've color coded the bottom row. Yep, the bottom row. Instead of starting at the top, why not look at it from another angle? Go ahead. Try to sum up some numbers, starting from the bottom.

No, actually, don't. This pyramid is too big. We can do better, and here's the key: We can break the pyramid into many small pyramids. Let's start from the bottom left, and take the first three-number sub-pyramid. Which of the two bottom ones is bigger? Add the bigger one to the number above. Shift one to the right, and do the same again.

When we're done with the bottom row, we can go up one row, and do the same thing again. The top numbers of the tiny pyramids we had last time, will now be the bottom row of our new -- still, just as tiny -- pyramids. Do this all the way to the top, and you end up with this:

There you have it. Sitting on its throne, at the very top, is the highest possible sum you can get by traversing the pyramid. I had to limit myself to 18 rows so the pyramid wouldn't overflow the page, and solving this pyramid only takes a few milliseconds. That said, you can easily solve pyramids with hundreds of rows like this. In fact, your computer solved the above pyramid as you loaded this page. It's randomly generated, and a new pyramid is generated (and solved) every time you refresh this page. You didn't even notice, did you?

Smaller pyramids can be solved by brute force. Though, for every row you add, you will dramatically increase the computation needed to find the best possible path. Just think about it. From the top, you have two choices. For each of those, you have two choices... And so it keeps branching off into the hundreds, thousands, millions, billions...

If you found this technique interesting, I recommend reading more about dynamic programming. There are plenty of cool ways you can solve problems like these by splitting the original problem into many smaller ones. The solution to the smaller, easier problems can be combined to solve more small problems up the chain.