Dynamic programming is simple #3 (multi-root recursion)

1. Dynamic programming is simple
2. Dynamic programming is simple #2
3. Dynamic programming is simple #3 (multi-root recursion) (this article)
4. Dynamic programming is simple #4 (bitmap + optimal solution reconstruction)

Now, when you got the idea, let’s look at one problem that doesn’t fit the pattern if you apply it blindly.

The solution to the problem I am about to show you might seem obvious to many of you if you followed the previous article. However, I’ve seen people who got stuck here because of a simple nuance.

The problem

We’re about to discuss this problem .

This one is one of the classic DP examples. It is relatively easy, so people already familiar with DP should come up with the solution almost immediately.

First attempt

Let’s try to write down the solution using the pattern we already know.

I’ll point out that the solution below is incorrect. Still, this is a solution I often see people implement and struggle to understand why it doesn’t work.

I’ll implement the top-down solution because it is simpler to see that way how the answer is formed.

It looks like everything is fine here. We have defined what we do each step (try to pick the next element in the array and add it to the existing subsequence), each step is valid, and the recursion itself is correct. So there is nothing wrong with recursion. Still, when we run this solution, it doesn’t work. What’s wrong here?

Many of you have already noticed the problem. The problem is that we consider only a subsequence that includes the first element of the nums array.

Let’s check the call graph to illustrate it better.

I hope it is clear now that by calling only dp(0), we're missing calling dp() at many other positions. We only call it for those positions, reachable from dp(0).

This is where it diverges a bit from the initial pattern. Earlier, for all the solutions to seed the recursion, we needed to only call dp() from some initial position (day 0 for "buying and selling stocks", and for edit distance, we just put pointers to 0 positions in both strings). This case is different because of how we defined the recursion step. That needs to be fixed from outside the recursive call.

Correct solution

You might already have come up with the fix, so I’ll just write the correct solution down.

Now we check all possible starting positions, and this gives us a correct answer.

Let’s check a new call graph.

Hooray! It works.

Let’s try to write down a bottom-up solution as well using the well-known set of transformation rules.

And now we’re done. Time to celebrate another solved dp problem.

Final thoughts

We have just done a one-dimensional example. Some multi-dimensional problems require the same technique. The general idea is that not always all the nodes in the DP table are reachable from just a single location. So the call graph is not a tree anymore as it was for the previous problems. Instead, it is a multi-root tree. To construct a solution, you should make queries from every possible tree root and choose the best results for a given problem statement. So one more step is added to your solution.

I’m not giving you the list of such problems intentionally. You should be able to recognize them yourself.

That’s it for now. In the following article, I’ll show how bitmasks might be helpful for DP problems. Stay tuned.

(more solved problems are available at )