There is a very interesting problem I recently came across as part of Google’s foobar challenge. The problem is called ‘zombie antidote’.

I wanted to write down some thoughts as I made my way towards solving this problem.

**Thoughts:**

- The problem smells like Dynamic Programming.
- However, there are some challenges in coming up with the DP solution
- How to build up the optimal substructure (aka. recurrence relation) for the problem ?
- How to show overlapping subproblem property ?

- It is useful to look at problems from different perspectives.
- E.g. Can the activity selection problem be formulated as a Graph theory problem ?

**Tips**:

- Refresh basics of Dynamic Programming Algos.
- Especially useful here was understanding the
** cut-rod problem **from Cormen’s algo book

- Understanding the relationship between the following 3 fundamental algorithmic approaches.
- Dynamic Programming
- Greedy Algorithms
- Graph Theory

- As it turns out, the activity selection problem can indeed be formulated in all of the 3 algo approaches listed above.

**Code:**

**References:**

- http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html
- http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/
- http://www.davebrundage.com/scheduling-problem-zombit-antidote/
- https://getpocket.com/a/read/808088510

### Like this:

Like Loading...