1 00:00:00,490 --> 00:00:01,660 Welcome back. 2 00:00:01,690 --> 00:00:08,140 We have discussed the recursive approach for solving the Liz question, and we have seen that the time 3 00:00:08,140 --> 00:00:12,040 complexity for this was of the order of two to the power n. 4 00:00:12,070 --> 00:00:15,190 Let's now see whether we can do better. 5 00:00:15,190 --> 00:00:18,100 So we proceed to the memoization approach. 6 00:00:18,100 --> 00:00:22,480 And remember memoization is just recursion plus storage. 7 00:00:22,480 --> 00:00:29,140 So we would be able to easily memoize the recursive approach that we have previously written by just 8 00:00:29,140 --> 00:00:31,240 adding a few lines of code. 9 00:00:31,270 --> 00:00:32,770 So let's discuss this. 10 00:00:33,590 --> 00:00:39,770 So over here we have the recursion tree that we had previously drawn for this problem, where the array 11 00:00:39,770 --> 00:00:42,020 that's given to us is one, two, three. 12 00:00:42,050 --> 00:00:49,910 Now how do we store things in a table in a way that we can avoid recomputing the same thing again and 13 00:00:49,910 --> 00:00:50,360 again. 14 00:00:50,360 --> 00:00:56,030 For example, notice over here the problem three comma two happened over here three times. 15 00:00:56,030 --> 00:00:58,250 And you have two comma one twice. 16 00:00:58,250 --> 00:01:06,050 Now with more complicated inputs, you will see that many subproblems are computed multiple times. 17 00:01:06,050 --> 00:01:10,220 And by just storing these we can avoid recomputation. 18 00:01:10,220 --> 00:01:12,740 And that's the memoization approach. 19 00:01:12,740 --> 00:01:15,980 Now for these notice that we have hit the base case. 20 00:01:15,980 --> 00:01:18,140 So we will not be storing this. 21 00:01:18,140 --> 00:01:25,940 Now let's think about how to store useful solutions to subproblems so that whenever we encounter them 22 00:01:25,940 --> 00:01:30,770 again in the future, we can just retrieve what we have stored and return it. 23 00:01:30,800 --> 00:01:37,370 Now for the list question, we can either use a 2D table or a 1D table. 24 00:01:37,370 --> 00:01:44,630 In this video, let's discuss the 2D approach and later when we are discussing tabulation, we will 25 00:01:44,630 --> 00:01:50,660 discuss first the 2D approach, and then we will also discuss the 1D array approach for solving the 26 00:01:50,660 --> 00:01:51,530 Liz question. 27 00:01:51,530 --> 00:01:55,460 So over here let's go with the more intuitive 2D approach. 28 00:01:55,460 --> 00:01:57,320 So I have a 2D array. 29 00:01:57,470 --> 00:02:04,790 And notice that on the columns part I have the indices for storing the previous index. 30 00:02:04,790 --> 00:02:10,790 And over here I have the rows indicating the current index that we are considering. 31 00:02:10,790 --> 00:02:17,540 Because remember for every recursive call over here we had these two parameters, the current index 32 00:02:17,540 --> 00:02:23,420 being considered and the previous index that was added to the subsequence at hand. 33 00:02:23,540 --> 00:02:32,270 Now the current index goes from the first index till the last index, which is zero to n minus one, 34 00:02:32,270 --> 00:02:34,610 and that's n values. 35 00:02:34,610 --> 00:02:43,550 But the value for the previous index, as we have discussed, goes from minus one up to n minus two. 36 00:02:44,290 --> 00:02:50,980 Minus one indicates that nothing has been added in the subsequence so far, and then it goes only up 37 00:02:50,980 --> 00:02:59,470 to n minus two, because prev has to be less than curr, and the last value for curr is n minus one, 38 00:02:59,470 --> 00:03:04,210 and therefore the value previous to this is going to be n minus two. 39 00:03:04,240 --> 00:03:10,900 So the value for the previous index ranges from minus one to n minus two. 40 00:03:10,930 --> 00:03:17,290 Now to store this in this 2D array we will offset these values by one. 41 00:03:17,290 --> 00:03:23,380 And we will change -1 to 0 by adding one to it. 42 00:03:23,380 --> 00:03:26,830 And n minus two becomes n minus one. 43 00:03:26,830 --> 00:03:29,710 So over here also we have n values. 44 00:03:29,710 --> 00:03:32,380 So let's write these indices over here. 45 00:03:32,380 --> 00:03:33,970 So we have zero over here. 46 00:03:34,770 --> 00:03:36,810 And then one and then two. 47 00:03:36,840 --> 00:03:43,110 So that's zero to n minus one for this problem and for cur we have the values from zero to n minus one. 48 00:03:43,110 --> 00:03:44,940 So zero, one and two. 49 00:03:44,970 --> 00:03:49,650 So we will use this 2D table to store things that we compute. 50 00:03:49,650 --> 00:03:57,060 And then when we need them again we will just retrieve from this 2D table in constant time and return 51 00:03:57,060 --> 00:03:57,600 the value. 52 00:03:57,600 --> 00:03:59,700 So that's the memoization approach. 53 00:03:59,730 --> 00:04:04,230 Initially we will fill all these cells with minus one. 54 00:04:04,230 --> 00:04:11,220 And then in each of these recursive calls after checking the base case, what we will do is we will 55 00:04:11,220 --> 00:04:16,170 check whether the subproblem in this table over here is minus one. 56 00:04:16,200 --> 00:04:21,420 If it's not minus one, if you see that, for example, when we have two comma one right. 57 00:04:21,420 --> 00:04:23,070 So we would have stored it over here. 58 00:04:23,070 --> 00:04:30,870 And then when we again come to two comma one over here, we will check whether this subproblem in the 59 00:04:30,870 --> 00:04:33,810 2D table is minus one or not. 60 00:04:34,660 --> 00:04:42,310 If you see that it's not minus one, then we would just return the value that we get from the 2D table. 61 00:04:42,340 --> 00:04:45,610 Now where would two comma one be stored over here. 62 00:04:45,640 --> 00:04:47,230 Let's take a quick look at that. 63 00:04:47,230 --> 00:04:49,810 So car over here is equal to two. 64 00:04:49,840 --> 00:04:53,740 So we have car equal to two and prev is equal to one. 65 00:04:53,740 --> 00:04:54,730 So this is prev. 66 00:04:54,730 --> 00:04:57,010 So when prev is equal to one. 67 00:04:57,010 --> 00:05:02,290 Remember when we store it in the DP table we have to offset it by one. 68 00:05:02,290 --> 00:05:04,000 So this becomes two. 69 00:05:04,030 --> 00:05:10,540 So the solution to two comma one will be stored over here which is at two two. 70 00:05:10,540 --> 00:05:14,170 Because remember again this two means prev is equal to one. 71 00:05:14,170 --> 00:05:16,360 This one means prev is equal to zero. 72 00:05:16,360 --> 00:05:22,660 And this zero means prev is equal to minus one, which indicates that nothing has been added in the 73 00:05:22,660 --> 00:05:24,190 subsequence at hand. 74 00:05:24,190 --> 00:05:29,950 So let's go ahead and see how we can implement this in code in the next video.