# This Dynamic Programming Problem will Challenge You.

#### Solving the Independent Set Problem

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.

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 **}:

### 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!

If you enjoyed this article, please make sure to Subscribe, Clap, Comment and Connect with me today! 🌐