1
00:00:00,110 --> 00:00:00,980
Welcome back.

2
00:00:00,980 --> 00:00:05,780
Now let's get into the memoization approach for solving the list question.

3
00:00:05,780 --> 00:00:09,170
And this is the recursive approach that we had previously written.

4
00:00:09,170 --> 00:00:15,110
And you will see that we would just need to add a few lines of code to get this changed to the memoization

5
00:00:15,110 --> 00:00:15,620
approach.

6
00:00:15,620 --> 00:00:17,000
So let's get started.

7
00:00:17,000 --> 00:00:24,110
First let's create a 2D dp array which will have n rows and n columns.

8
00:00:24,110 --> 00:00:24,380
Okay.

9
00:00:24,380 --> 00:00:25,460
So let's do that.

10
00:00:27,790 --> 00:00:33,340
So we'll have n rows and we would need n plus one columns.

11
00:00:34,120 --> 00:00:34,630
Okay.

12
00:00:34,630 --> 00:00:40,780
And what we will do is we will fill every cell in this 2D dp array with the value minus one.

13
00:00:40,990 --> 00:00:41,770
All right.

14
00:00:41,770 --> 00:00:48,490
Now over here in the helper function after the base case before we go ahead and do these computations

15
00:00:48,490 --> 00:00:54,280
over here, we will check whether we had previously computed this particular scenario and stored it

16
00:00:54,280 --> 00:00:55,450
in our DP table.

17
00:00:55,450 --> 00:01:07,120
So we'll say if dp at curr and prev plus one is not equal to minus one, then we will just return.

18
00:01:07,120 --> 00:01:14,980
We don't need to again compute it, but we will just return dp at curr and prev plus one okay.

19
00:01:14,980 --> 00:01:17,500
And again notice we have pref plus one over here.

20
00:01:17,500 --> 00:01:20,410
And we have discussed why this is the case in the previous video.

21
00:01:20,410 --> 00:01:22,360
But let me quickly review it.

22
00:01:22,360 --> 00:01:24,880
Remember prev starts with minus one.

23
00:01:24,880 --> 00:01:30,880
So that's why we always have to increase it by one so that the values for prev starts from zero and

24
00:01:30,880 --> 00:01:32,320
then it goes up to n.

25
00:01:32,320 --> 00:01:32,710
Okay.

26
00:01:32,710 --> 00:01:38,650
So again the typical values for prev are from minus one up to n minus one.

27
00:01:38,650 --> 00:01:42,280
And when you add one to it it changes to zero to n.

28
00:01:42,280 --> 00:01:42,700
Okay.

29
00:01:42,700 --> 00:01:47,710
So that's why we have everywhere where we are referring this we will have prev plus one.

30
00:01:47,710 --> 00:01:49,090
Now let's continue.

31
00:01:49,090 --> 00:01:55,270
Now if this is not the case then we would have to go ahead and compute the exclude value and the include

32
00:01:55,270 --> 00:01:55,660
value.

33
00:01:55,660 --> 00:01:57,730
Now let's say we have both of these.

34
00:01:57,730 --> 00:02:02,020
And before we return this over here we will store it okay.

35
00:02:02,020 --> 00:02:02,710
So let's do that.

36
00:02:02,710 --> 00:02:03,880
So we can store it.

37
00:02:03,880 --> 00:02:12,280
We can say dp at curr and prev plus one is equal to math dot max include and exclude okay.

38
00:02:12,280 --> 00:02:17,110
The greater value between these two will be stored at DP at current prev plus one.

39
00:02:17,110 --> 00:02:20,710
And then we can just return dp curr prev plus one.

40
00:02:20,710 --> 00:02:21,190
All right.

41
00:02:21,190 --> 00:02:24,700
So this is the memoization approach for solving this question.

42
00:02:24,700 --> 00:02:30,610
And notice that we just had to add a few lines of code to change the recursive approach to the memoization

43
00:02:30,610 --> 00:02:31,150
approach.

44
00:02:31,150 --> 00:02:35,650
Now let's go ahead and run this code and see if it's passing all the test cases.

45
00:02:37,210 --> 00:02:40,060
And you can see that it's passing all the test cases.