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.
- 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 ?
- 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.