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.
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
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)
With the warning of problem 67 in mind, I set out to tackle this problem with a somewhat efficient solution which will also work for problem 67. To start off, let’s look at the simple example, as you traverse down the triangle from the top you have two options at every turn – go left, or go right. From the third row onwards, some of the paths will end up in the same place in the triangle:
From the above image you can see that the path 3-7-4 and 3-4-4 both exit the mini triangle at the same location but carrying two different totals – green = 14, red = 11. If you were to continue down the triangle from this point on, regardless of whether you’re going to turn left or right in the next move, the max total will surely have to come from the path which has generated the highest total so far.
If we apply the same logic to the entire triangle we can build up a triangle of totals for the raw triangle where every element represents the max total achievable by any path that has lead to it:
Let’s call this triangle of totals T, and the original triangle R, we have:
You can see that T(2,1) differed from T(2,0) and T(2,2) in that it required us to find the greater between T(1,0) and T(1,1). For simplicity sake, let’s say that for a given row n, in T (where n >= 2) we have:
The max total from top to bottom of the triangle R is equal to the max total in the last row of the triangle T. Seeing as we’re only interested in the max total rather than the triangle T itself, my solution below only returns the last row of T which is all we need to solve the problem:
I specialise in rapidly transitioning teams to serverless and building production-ready services on AWS.
Are you struggling with serverless or need guidance on best practices? Do you want someone to review your architecture and help you avoid costly mistakes down the line? Whatever the case, I’m here to help.
Check out my new course, Complete Guide to AWS Step Functions. In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. Including basic concepts, HTTP and event triggers, activities, callbacks, nested workflows, design patterns and best practices.
Here is a complete list of all my posts on serverless and AWS Lambda. In the meantime, here are a few of my most popular blog posts.
- Lambda optimization tip – enable HTTP keep-alive
- You are thinking about serverless costs all wrong
- Many faced threats to Serverless security
- We can do better than percentile latencies
- I’m afraid you’re thinking about AWS Lambda cold starts all wrong
- Yubl’s road to Serverless
- AWS Lambda – should you have few monolithic functions or many single-purposed functions?
- AWS Lambda – compare coldstart time with different languages, memory and code sizes
- Guys, we’re doing pagination wrong