1
00:00:00,590 --> 00:00:01,730
Welcome back.

2
00:00:01,940 --> 00:00:08,240
We will use the Fibonacci question to get started with dynamic programming.

3
00:00:08,270 --> 00:00:15,200
Remember previously when we had discussed what questions can be solved using dynamic programming?

4
00:00:15,200 --> 00:00:21,650
We had discussed that the Fibonacci coding interview question has the two necessary characteristics

5
00:00:21,650 --> 00:00:28,370
of any dynamic programming question, which are overlapping subproblems and optimal substructure.

6
00:00:28,400 --> 00:00:29,690
So let's get started.

7
00:00:29,690 --> 00:00:33,320
And the approach that we will take will have four steps.

8
00:00:33,320 --> 00:00:38,210
First, we will write the recursive solution to this coding interview problem.

9
00:00:38,210 --> 00:00:40,250
Then we will memorize it.

10
00:00:40,250 --> 00:00:44,420
And then we will come up with the tabulation or bottom up approach.

11
00:00:44,420 --> 00:00:49,460
And finally we will write the space optimized tabulation approach.

12
00:00:49,460 --> 00:00:56,480
So let's get started with writing these four approaches for the Fibonacci coding interview question.