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

2
00:00:00,980 --> 00:00:05,210
Now this is the recursive solution that we had written previously.

3
00:00:05,240 --> 00:00:07,730
Now let's go ahead and memoize this.

4
00:00:07,730 --> 00:00:12,650
And you will note that we just need to add a few lines of code to achieve that.

5
00:00:12,650 --> 00:00:16,370
Now to start with let's create a DP array.

6
00:00:16,820 --> 00:00:17,210
Okay.

7
00:00:17,210 --> 00:00:20,090
So this is going to be a 2D array.

8
00:00:20,090 --> 00:00:25,160
And this will have n rows and w plus one columns.

9
00:00:25,160 --> 00:00:27,980
So let's go ahead and create this 2D array.

10
00:00:28,010 --> 00:00:29,960
Now again let me write this over here.

11
00:00:29,960 --> 00:00:35,480
It will have n rows and w plus one columns.

12
00:00:36,860 --> 00:00:45,380
So I can say const dp is equal to array dot from length n.

13
00:00:48,720 --> 00:00:55,380
Okay, so so far this creates n rows or n elements in the array.

14
00:00:55,380 --> 00:01:00,270
And then each element has to be an array of size w plus one.

15
00:01:00,750 --> 00:01:04,440
So this will ensure that we are creating a 2D DP array.

16
00:01:05,730 --> 00:01:12,810
And over here the size has to be w plus one because we want w plus one columns okay.

17
00:01:12,810 --> 00:01:20,190
And we are also going to fill each of the cells in this 2D dp array with the value minus one.

18
00:01:20,190 --> 00:01:25,290
So that's what we typically do when we write the memoization solution okay.

19
00:01:25,560 --> 00:01:30,900
And again we know that that will help us check over here after the base case whether we have already

20
00:01:30,900 --> 00:01:32,370
computed this or not.

21
00:01:32,370 --> 00:01:33,030
All right.

22
00:01:33,030 --> 00:01:35,790
So so far we have created this DP array.

23
00:01:35,790 --> 00:01:42,690
Now after the base case over here before we go ahead and compute this part, let's first check whether

24
00:01:42,690 --> 00:01:49,290
we had previously computed and stored the value for this particular index and remaining weight.

25
00:01:49,290 --> 00:02:02,250
So we can say if dp at index and remaining weight is not equal to minus one, it would mean that we

26
00:02:02,250 --> 00:02:04,650
already computed and stored this value.

27
00:02:04,650 --> 00:02:10,530
Otherwise it has to be minus one, because we have already filled all the cells in the 2d dp array with

28
00:02:10,530 --> 00:02:11,490
the value minus one.

29
00:02:11,490 --> 00:02:19,530
So if this is not equal to minus one, then we will just return dp at index and remaining weight.

30
00:02:20,520 --> 00:02:21,150
All right.

31
00:02:21,150 --> 00:02:24,750
Now if this is not the case then we proceed.

32
00:02:24,750 --> 00:02:29,430
We calculate exclude and include and then this also goes as it is.

33
00:02:29,430 --> 00:02:33,270
But then before we return this we are going to store it okay.

34
00:02:33,270 --> 00:02:34,680
So we are going to store it over here.

35
00:02:34,680 --> 00:02:37,140
We'll say DP at index.

36
00:02:37,440 --> 00:02:46,440
And remaining weight is equal to what we have over here which is the maximum between exclude and include

37
00:02:46,440 --> 00:02:51,150
and then we will just return DP at index and remaining weight.

38
00:02:51,480 --> 00:02:53,850
So we will return this and that's it.

39
00:02:53,850 --> 00:03:00,720
So notice how with just a few lines of code we were able to memorize the recursive solution.

40
00:03:00,720 --> 00:03:05,640
Now let's go ahead and run this code and see if it's passing all the test cases.

41
00:03:07,470 --> 00:03:09,450
And you can see that it's working.

42
00:03:09,450 --> 00:03:10,770
It's passing all the test cases.