Dynamic programming is an intimidating subject to grasp; even more, intimidating to get in a technical interview. This post will help you understand exactly what it is, when to use it, and how to use it.
Before getting into the specifics we should briefly define what dynamic programming is.
Dynamic programming is a way to optimize the time complexity of a recursive algorithm by caching previously calculated results.
There are a few more nuanced complexities to dynamic programming than this, but it’s a sufficient base to go off for now. The most important rule to keep in mind is that you can only use it if problems have optimal substructure.
What is optimal substructure? Optimal substructure is a shared property among subproblems. More specifically it is the shared property that solutions to larger subproblems are built on top of the solutions to smaller subproblems. A fantastic example of this is the Fibonacci Sequence.
The Fibonacci Sequence is defined as the nᵗʰ number in the sequence is equal to the sum of n − 1 and n− 2. So the fifth number in the Fibonacci Sequence is 5.
Fibonacci Sequence for First 5 Numbers
1, 1, 2, 3, 5More specifically we can define the recurrence relation of the Fibonacci Sequence as
