1
00:00:00,080 --> 00:00:00,950
Welcome back.

2
00:00:00,950 --> 00:00:08,240
So this is the code that we had previously written for writing the recursive solution for the LCS question.

3
00:00:08,240 --> 00:00:10,610
Now let's go ahead and memorize this.

4
00:00:10,610 --> 00:00:11,990
And you will see that.

5
00:00:11,990 --> 00:00:15,890
To achieve that we would just need to add a few lines of code.

6
00:00:15,890 --> 00:00:23,750
To start with, let's create a 2D dp array which will have n rows and n columns okay.

7
00:00:23,750 --> 00:00:24,740
So let's do that.

8
00:00:29,270 --> 00:00:30,410
Length in okay.

9
00:00:30,410 --> 00:00:35,540
So it will have n rows and we need it to have m columns.

10
00:00:35,540 --> 00:00:36,830
So let's do that.

11
00:00:37,730 --> 00:00:44,420
And what we are doing is we are going to fill every cell in this 2D dp array with the value minus one.

12
00:00:45,450 --> 00:00:51,750
And you will have noticed that this is something pretty common across problems where we memoize a solution.

13
00:00:51,750 --> 00:00:57,570
Again, this is useful because we can check whether we have previously computed something or not using

14
00:00:57,570 --> 00:00:57,990
this.

15
00:00:57,990 --> 00:01:03,690
Okay, now after creating the DP array, let's go ahead and modify the helper function slightly.

16
00:01:03,690 --> 00:01:10,620
So after the base case, before we go ahead and compute the recursive case, we will check whether we

17
00:01:10,620 --> 00:01:17,520
had previously computed and stored this particular index one index two combination in the DP array or

18
00:01:17,520 --> 00:01:18,000
not.

19
00:01:18,000 --> 00:01:28,410
Okay, so we'll say if dp at index one index two not equal to minus one okay.

20
00:01:28,410 --> 00:01:35,040
So if it's not equal to minus one it means that we have previously computed and stored this value in

21
00:01:35,040 --> 00:01:36,000
the DP array.

22
00:01:36,000 --> 00:01:37,650
And that's why it's not minus one.

23
00:01:37,650 --> 00:01:43,380
Because over here we had filled every cell in the DP array with the value minus one okay.

24
00:01:43,380 --> 00:01:50,130
So if this is not equal to minus one then we will just return dp at index one.

25
00:01:51,000 --> 00:01:53,700
Index two okay.

26
00:01:54,150 --> 00:01:58,410
Now if this is not the case then we proceed with the recursive case.

27
00:01:58,410 --> 00:02:05,670
So over here if text one at index one is equal to text two at index two, then we will not return this,

28
00:02:05,670 --> 00:02:09,690
but rather we will store this in dp at index one index two.

29
00:02:09,690 --> 00:02:18,390
So over here and say dp at index one, index two is equal to one plus whatever we get back from this

30
00:02:18,390 --> 00:02:19,920
recursive call okay.

31
00:02:19,920 --> 00:02:21,960
Now if this is not the case.

32
00:02:21,960 --> 00:02:23,850
So let's write an else statement over here.

33
00:02:23,850 --> 00:02:28,290
So if this is not the case then we'll say dp at index one.

34
00:02:29,550 --> 00:02:34,740
Index two is equal to whatever we get over here.

35
00:02:35,070 --> 00:02:36,420
So let me copy this.

36
00:02:36,420 --> 00:02:37,770
Let me cut and copy this.

37
00:02:37,770 --> 00:02:40,260
And I'm pasting it over here okay.

38
00:02:40,260 --> 00:02:45,780
And after that over here when we come over here we'll just return DP at index one.

39
00:02:47,520 --> 00:02:48,240
Index two.

40
00:02:49,110 --> 00:02:50,370
And that's it okay.

41
00:02:50,370 --> 00:02:56,370
So notice that we were able to memorize the recursive approach by just adding a few lines of code.

42
00:02:56,370 --> 00:03:00,360
Now let's go ahead and run this code and see if it's passing all the test cases.

43
00:03:01,140 --> 00:03:03,150
And you can see that it's working.

44
00:03:03,150 --> 00:03:04,920
It's passing all the test cases.