This Dynamic Programming Problem will Challenge You.

Dynamic Programming is a fundamental programming technique every developer should have in their arsenal.

I believe solving DP problems is the only way to improve at a fast rate.

So today we will tackle the independent Set problem!

If you need an introduction to Dynamic Programming, feel free to check out my previous article.

Without further ado, lets dive right in!

Understanding the Problem

Consider a weighted graph that forms a linear chain of vertices from node0 → node7 as follows.

A weighted graph with a linear chain of vertices

Our goal is to find the independent subset of graph nodes such that:

There are no connections between adjacent nodes.
The total weight is maximized.

E.g. In this example, the independent subset is { node1, node3, node6 }:

A weighted graph with a linear chain of vertices (optimal solution)

Modelling the Data

Lets translate our understanding of the problem into code!

Start by defining a type DpNode which represents a weighted graph vertex.

To represent an array of DpNodes, define another type NodeArray:

Lastly, let’s create a NodeArray representing the graph from the diagram.

Finding the Recurrence Relation

Before jumping into code, we must relate the original problem and it’s subproblems recursively.

Let opt[n] be the optimal value for a graph of n+1 nodes (since arrays are 0 indexed).

Begin by working backwards from the last node.

Regarding the last node, there are only two possibilities:

Either the last node contributed to opt[n]
Or the last node didn’t contribute.

If case 1 is true:

opt[n] = node[n].weight + opt[n - 2]

We add the weight of the last node, since it’s in the optimal solution.
We then solve opt[n - 2], as opt[n - 1] would now form a connection between adjacent nodes, which is not allowed.

If case 2 is true:

opt[n] = opt[n - 1]

Any node from 0 to n-1 may contribute to the optimal solution.

Considering both cases:

We want the max value attained from either case, so we end up with this final recurrence relation:

opt[n] = max(opt[n — 1], nodes[n].weight + opt[n — 2])

Finding the Optimal Solution

If you understand the recurrence relation, which is the hardest part, implementing the code should be trivial.

To calculate the optimal values, we will use the Bottom-up DP approach:

Note that this function optVal will return every optimal value.

However, we want the independent subset of nodes that contributed to the optimal values.

To do this:

We iterate backwards from last optimal value
We compare adjacent optimal values.
If the latter > former, node i must be in the optimal solution, hence add it to a set S and decrement i by 2.
Else, decrement i by 1.

Conclusion

I hope you found this problem challenging and informative!

Dynamic Programming is a difficult topic in Computer Science, and I hope I made this example as clear as possible.

More Dynamic Programming tutorials will be released in due course, so stay tuned!