Welcome back.
We will use the Fibonacci question to get started with dynamic programming.
Remember previously when we had discussed what questions can be solved using dynamic programming?
We had discussed that the Fibonacci coding interview question has the two necessary characteristics
of any dynamic programming question, which are overlapping subproblems and optimal substructure.
So let's get started.
And the approach that we will take will have four steps.
First, we will write the recursive solution to this coding interview problem.
Then we will memorize it.
And then we will come up with the tabulation or bottom up approach.
And finally we will write the space optimized tabulation approach.
So let's get started with writing these four approaches for the Fibonacci coding interview question.