1
00:00:00,690 --> 00:00:02,700
Hey there and welcome back!

2
00:00:02,730 --> 00:00:09,660
In the previous video, we discussed that writing the recursive solution helps us to come up with the

3
00:00:09,660 --> 00:00:13,080
bottom up approach or the tabulation approach.

4
00:00:14,880 --> 00:00:17,010
Now, why is this the case?

5
00:00:17,630 --> 00:00:25,100
The best way to understand this is by showing the benefits of this in an actual coding interview question,

6
00:00:25,100 --> 00:00:31,730
and we will see this in action soon when we start attempting dynamic programming coding interview questions.

7
00:00:31,730 --> 00:00:35,510
But over here, let me give you three reasons.

8
00:00:35,510 --> 00:00:42,140
The first reason is that writing the recursive solution first helps us to understand the subproblems.

9
00:00:42,140 --> 00:00:50,000
It also helps us to understand the transition formula as well as it helps us to recognize the necessary

10
00:00:50,000 --> 00:00:50,930
base condition.

11
00:00:50,930 --> 00:00:54,140
And this also can be used in some interesting way.

12
00:00:54,140 --> 00:00:56,660
When we come up with the tabulation approach.

13
00:00:56,660 --> 00:00:59,690
Let's take a quick look at these three points over here.

14
00:00:59,690 --> 00:01:02,090
And we are just getting introduced to these.

15
00:01:02,090 --> 00:01:09,140
And you will be able to solidify what we mean over here when we actually start solving dynamic programming

16
00:01:09,140 --> 00:01:10,400
coding interview questions.

17
00:01:10,400 --> 00:01:11,660
So let's get started.

18
00:01:11,660 --> 00:01:18,680
So the first benefit is that writing the recursive solution helps to understand the subproblems.

19
00:01:18,680 --> 00:01:25,250
Any recursive solution inherently breaks down a problem into smaller subproblems.

20
00:01:25,250 --> 00:01:31,520
And because of that, if we first write the recursive solution, we will develop a clear understanding

21
00:01:31,520 --> 00:01:36,020
of what these subproblems are for the coding question at hand.

22
00:01:36,470 --> 00:01:44,720
The second benefit of writing the recursive solution first is that it helps us to understand the transition

23
00:01:44,720 --> 00:01:45,410
formula.

24
00:01:45,410 --> 00:01:53,090
With transition formula, we mean how do we use the subproblems or solutions to the subproblems to come

25
00:01:53,090 --> 00:01:55,850
up with the solution to the original problem?

26
00:01:55,850 --> 00:02:04,130
Now, the way the recursive calls are made helps us in identifying the transition formula or the recurrence

27
00:02:04,130 --> 00:02:04,910
relation.

28
00:02:04,910 --> 00:02:09,560
Now this is another benefit of first writing the recursive solution.

29
00:02:09,980 --> 00:02:16,640
Finally, if we first write the recursive solution, we would have written the base conditions, because

30
00:02:16,640 --> 00:02:19,610
any recursive solution has a base case.

31
00:02:19,610 --> 00:02:26,630
And when we come up with the bottom up approach or the tabulation approach, the base case over here

32
00:02:26,630 --> 00:02:33,470
or the base conditions over here would be the initial conditions in your dynamic programming table.

33
00:02:33,470 --> 00:02:40,040
Now, what a dynamic programming table is, is something that we will soon see when we start to solve

34
00:02:40,040 --> 00:02:41,060
DP problems.

35
00:02:41,060 --> 00:02:44,210
But again, over here we are just developing an intuition.

36
00:02:44,210 --> 00:02:50,900
So do remember that when we come up with the bottom up or tabulation approach, as the name suggests,

37
00:02:50,900 --> 00:02:53,720
over here we will be having a DP table.

38
00:02:53,720 --> 00:02:59,600
And then in many cases it's very easy if you have written the recursive solution first, because we

39
00:02:59,600 --> 00:03:06,680
can just use the base case of the recursive solution to fill out the initial conditions in the DP table,

40
00:03:06,680 --> 00:03:11,570
which is typically something that we fill over here, like for example, these rows would be initialized

41
00:03:11,570 --> 00:03:16,040
to zero, etc. and again it varies based on the coding interview question.

42
00:03:16,340 --> 00:03:23,030
In the next video, let's go ahead and discuss how can we identify whether a coding interview question

43
00:03:23,030 --> 00:03:26,540
is to be solved using dynamic programming or not?

44
00:03:26,540 --> 00:03:34,490
And then we'll get started with applying all that we learned in solving actual DP coding interview problems.