Dynamic programming is simple #4 (bitmap + optimal solution reconstruction)

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

After a long break, I finally found some time to return to this series of articles. There are still a couple of corner cases left to describe.

This time I’ll be talking about the case when the recursion arguments can’t be naturally cached. Also, you will learn not only how to find minimum/maximum but how to reconstruct the optimal solution as well.

Problem

There are quite some problems requiring the method I’m about to describe. I picked the one that, in addition to illustrating the technique, also requires doing one thing we haven’t done before: reconstruction of an optimal solution.

Here is the problem

Short description of the task: we have a number of people, each of them has a certain set of skills, and we want to create a minimum possible team, so each skill is mastered by at least one person in the team.

Backtracking solution

Bruteforce solution for this task is pretty straightforward. Each time we can make one of 2 decisions: