Rather than explaining what dynamic programming is-just use Google for that-I’ll make it clearer through an example. It’s not that hard of a concept, a priori, once you get the the idea behind it and you’ve done a few practice problems with it.
Look at Problem #18 in Project Euler. You could brute-force this by searching all the paths, but you will eventually run into a sister problem on #67 that isn’t so amenable to this. So, let’s get two problems for the price of one. For the sake of brevity, I’ll use the short triangle given in the prompt as our test case.
(FYI: Always, always, always do smaller test cases on these kinds of problems first as a sanity check.)
3
4 7
2 4 6
8 5 9 3
OK, how can we tackle this without brute-forcing it? Well… we want the maximum path, right? So… why don’t we take the local maximum of the two choices ahead of us, in a greedy approach?
10
4 6
5 9 3
We encode the first step of the path within the first entry of the triangle, thus fully accounting for it! It is not necessary to traverse every path. Similarly, we take the max of the next two options, and then the maximum of the next choice, until we are left with the answer.
16
9 3 → 23.
This does give us the right answer. However, it won’t work for all cases. Suppose we have:
4
2 5
10 1 3
We’ll miss out on the the maximum path-the one with the 10-following the above approach. Nevertheless, we are beginning to get close: we want to somehow save the information that we have already calculated, thus relieving us of the need to traverse every single path.
Let’s start from the bottom instead, using this above example. Assuming a triangle of depth n, let’s start on the (n-1)th level.
4
2 5 → 4 → 16
10 1 3 12 8
For each row, you will calculate the sum of the element and the maximum of the two elements below it. Eventually, since you’ve calculated the optimal result of each possible path already, you will end up with the highest possible path at the root!
This is dynamic programming in action. By saving the result to every subproblem, we can use the previous calculation to shorten the job in the future. This is a great weapon to have in your toolbox for problems where you have lots of similar, overlapping subproblems. It’s also highly efficient compared to old fashioned recursive methods-in some cases, like this one, it can reduce your complexity from factorial to quadratic.
Leaving The Undergound 