1 00:00:00,170 --> 00:00:07,160 Let's first discuss how can we identify that the Liz question is a DP question. 2 00:00:07,160 --> 00:00:10,850 And then let's proceed with the approach of solving this question. 3 00:00:10,850 --> 00:00:17,900 So for identifying the Liz question as a DP question, notice that we have two hints. 4 00:00:17,900 --> 00:00:25,190 First, we are asked an optimal solution because we are asked to find the longest increasing subsequence 5 00:00:25,190 --> 00:00:25,640 length. 6 00:00:25,640 --> 00:00:30,470 So longest over here indicates that we are trying to find an optimal solution. 7 00:00:30,470 --> 00:00:32,090 And we had previously discussed that. 8 00:00:32,090 --> 00:00:38,540 This is one of the hints that can be used to identify questions that can be solved with dynamic programming. 9 00:00:38,540 --> 00:00:42,860 The second hint over here is that we have choices at hand. 10 00:00:42,860 --> 00:00:49,820 So for example, to form a subsequence, we can either include an element or exclude an element from 11 00:00:49,820 --> 00:00:51,200 the array which is given to us. 12 00:00:51,200 --> 00:00:52,430 So we have choices. 13 00:00:52,430 --> 00:00:55,700 So this indicates that we could solve this with recursion. 14 00:00:55,700 --> 00:00:59,510 And we also see that we have two branches like. 15 00:00:59,510 --> 00:01:05,630 Let's say we start at a particular index and we exclude and we include and then we go to the next index. 16 00:01:05,630 --> 00:01:09,230 So again we have the options of excluding or including. 17 00:01:09,230 --> 00:01:15,200 And we had previously seen that especially when you have choices and when you have a tree that looks 18 00:01:15,200 --> 00:01:21,140 like this where you have multiple branches, there is a high probability for having overlapping subproblems. 19 00:01:21,140 --> 00:01:26,390 And hence probably the question could be solved using dynamic programming. 20 00:01:26,390 --> 00:01:31,460 Now let's get started with how to approach solving this question. 21 00:01:31,700 --> 00:01:36,110 We have understood that we want to solve this with dynamic programming. 22 00:01:36,110 --> 00:01:44,090 But remember, it's very difficult to start with the bottom up or tabulation approach directly. 23 00:01:44,090 --> 00:01:45,110 Don't do that. 24 00:01:45,110 --> 00:01:51,470 If it's a question that you're trying to solve for the first time, or especially if the variant that 25 00:01:51,470 --> 00:01:55,010 you're trying is not something that you've encountered previously. 26 00:01:55,010 --> 00:02:01,190 So if that is the case, the best approach for solving DP questions is first to write the recursive 27 00:02:01,190 --> 00:02:06,680 solution, then come up with the memoization approach, and then finally come up with the bottom up 28 00:02:06,680 --> 00:02:08,030 or tabulation approach. 29 00:02:08,030 --> 00:02:12,080 So this is the methodology that we will use over here as well. 30 00:02:12,080 --> 00:02:18,650 And again the advantage is that if you solve DP questions in this manner, you will be able to solve 31 00:02:18,650 --> 00:02:23,900 even new questions or questions that you have not previously encountered successfully. 32 00:02:23,900 --> 00:02:25,040 So let's get started. 33 00:02:25,040 --> 00:02:26,870 First with the recursion approach. 34 00:02:26,870 --> 00:02:33,980 Now, in the recursive approach, we'll have to think of what the base case is and what the recursive 35 00:02:33,980 --> 00:02:34,970 case is. 36 00:02:35,060 --> 00:02:42,740 Now remember, recursive solutions can be written either going from zero to n or n to zero. 37 00:02:42,830 --> 00:02:46,910 Over here, let's take the approach where we are going from zero to n. 38 00:02:46,910 --> 00:02:50,540 Now to discuss the recursive approach, let's take an example. 39 00:02:50,540 --> 00:02:54,290 Let's say the array which is given to us is one, two, three. 40 00:02:54,290 --> 00:02:59,540 Now first let's come up with the choice diagram to identify the recursive case. 41 00:02:59,540 --> 00:03:02,450 And again this is helpful because we have choices at hand. 42 00:03:02,450 --> 00:03:08,120 And it's always helpful to visualize the choices that we have using a choice diagram. 43 00:03:08,120 --> 00:03:17,690 Now remember whenever we consider including or excluding a particular element, it's important to know 44 00:03:17,690 --> 00:03:22,220 which element was previously included in the subsequence. 45 00:03:22,220 --> 00:03:27,050 And for that we need to know the index of the previously included element. 46 00:03:27,050 --> 00:03:33,620 And this is needed because the question says that we need to form a strictly increasing subsequence. 47 00:03:33,620 --> 00:03:37,400 So let's say previously we had included an element two. 48 00:03:37,430 --> 00:03:43,190 Then if this is the last included element, any further element that's going to be included in this 49 00:03:43,190 --> 00:03:46,610 subsequence has to be greater than this value over here. 50 00:03:46,610 --> 00:03:51,680 So that's why we need to remember the previously included elements index. 51 00:03:51,680 --> 00:03:56,000 So this is something that we need to keep in mind now to understand this in a good manner. 52 00:03:56,000 --> 00:03:57,410 Let's take an example. 53 00:03:57,410 --> 00:03:59,960 So we have the example 123 over here. 54 00:03:59,960 --> 00:04:04,130 And let's say we are considering to include the element two. 55 00:04:04,460 --> 00:04:04,880 All right. 56 00:04:04,880 --> 00:04:06,830 So let's say this is the current element. 57 00:04:06,830 --> 00:04:12,620 And to know whether we can include this in the subsequence that we are building, we need to know the 58 00:04:12,620 --> 00:04:14,420 previously included element. 59 00:04:14,420 --> 00:04:20,360 And for the sake of this example, let's say that one was previously included in the subsequence that 60 00:04:20,360 --> 00:04:21,410 we are building now. 61 00:04:21,410 --> 00:04:27,620 Over here we see that two is greater than one, and therefore we know that we can include two in the 62 00:04:27,620 --> 00:04:29,510 subsequence that we are considering. 63 00:04:29,510 --> 00:04:37,190 And when we include two in the subsequence, notice that the length of the subsequence increases by 64 00:04:37,190 --> 00:04:37,700 one. 65 00:04:38,270 --> 00:04:43,190 So this is something that we will keep in mind to come up with the recursive solution. 66 00:04:43,190 --> 00:04:49,040 Now remember, for each element in the array which is given to us, we have two possibilities. 67 00:04:49,040 --> 00:04:55,280 The first possibility is to include it in a subsequence, and the second possibility is to exclude it. 68 00:04:55,310 --> 00:04:58,880 Now we can always exclude an element from a subsequence. 69 00:04:58,880 --> 00:04:59,870 That's not a problem. 70 00:05:00,200 --> 00:05:07,070 But to include an element in a subsequence, the element at hand has to be greater than the last included 71 00:05:07,070 --> 00:05:08,720 element in the subsequence. 72 00:05:08,720 --> 00:05:15,020 So we just need to go over all the elements in the array which is given to us, and then we have these 73 00:05:15,020 --> 00:05:20,150 two choices for each element that is either included or excluded. 74 00:05:20,180 --> 00:05:26,330 Now if we just go through all the elements of the subsequence which is given to us, and if we just 75 00:05:26,330 --> 00:05:33,350 do, these two choices include and exclude and proceed to the next available index, we would get all 76 00:05:33,350 --> 00:05:35,180 the possible subsequences. 77 00:05:35,210 --> 00:05:43,010 Now, if we get all the possible subsequences, we can find the length of the longest increasing subsequence 78 00:05:43,010 --> 00:05:45,770 by just taking the maximum value. 79 00:05:45,770 --> 00:05:52,430 If we ensure that every subsequence formed follows the rule of being strictly increasing. 80 00:05:52,460 --> 00:05:58,700 Now, before we proceed and do a dry run of the approach that we are going to implement for the recursive 81 00:05:58,700 --> 00:06:05,390 solution, let's just take a moment to build our intuition to understand whether this is true. 82 00:06:05,390 --> 00:06:11,510 Is it really true that if we just go through every element in the array which is given to us, and if 83 00:06:11,510 --> 00:06:17,360 we do these two choices, that is, include the element and exclude the element, is it really true 84 00:06:17,360 --> 00:06:20,450 that we would get all the possible subsequences? 85 00:06:20,450 --> 00:06:23,780 Now for this we have this example over here 123. 86 00:06:23,780 --> 00:06:25,970 Now initially we are at the element. 87 00:06:25,970 --> 00:06:28,340 At index zero we exclude. 88 00:06:28,340 --> 00:06:29,780 We get an empty array. 89 00:06:29,780 --> 00:06:30,920 We include one. 90 00:06:30,920 --> 00:06:34,130 We get an array with one we proceed to the next element. 91 00:06:34,130 --> 00:06:35,600 Now we exclude. 92 00:06:35,600 --> 00:06:37,010 We get again an empty array. 93 00:06:37,010 --> 00:06:38,150 We include two. 94 00:06:38,180 --> 00:06:40,760 We get two over here and over here. 95 00:06:40,760 --> 00:06:42,500 When we exclude we get one. 96 00:06:42,500 --> 00:06:45,470 And when we include two, we get one and two. 97 00:06:45,470 --> 00:06:48,140 And then finally we do the same thing with three. 98 00:06:48,140 --> 00:06:52,610 And notice that these are the subsequences that we are getting. 99 00:06:52,610 --> 00:07:00,590 And this in fact has given us a list of all the possible subsequences that can be formed from this array 100 00:07:00,590 --> 00:07:01,340 over here. 101 00:07:01,340 --> 00:07:06,500 Now, when we do this, we will not blindly include every element as we've discussed. 102 00:07:06,500 --> 00:07:12,830 We will have the check that the element at hand has to be greater than the previously included element. 103 00:07:12,830 --> 00:07:19,220 But over here, we were just building the intuition that just by including and excluding elements and 104 00:07:19,220 --> 00:07:25,910 by going over all the elements in the array which is given to us, we can in fact get all the possible 105 00:07:25,910 --> 00:07:26,990 subsequences. 106 00:07:27,230 --> 00:07:31,430 Now we have discussed the choice diagram and we have built an intuition. 107 00:07:31,430 --> 00:07:37,100 So we're just going to exclude and include elements and go over all the elements in the array which 108 00:07:37,100 --> 00:07:38,060 is given to us. 109 00:07:38,060 --> 00:07:40,070 We've also discussed that before. 110 00:07:40,070 --> 00:07:41,690 We include an element. 111 00:07:41,690 --> 00:07:48,410 We will check whether the value at hand is greater than the previously included element. 112 00:07:48,410 --> 00:07:51,530 So more of that coming soon in the next video. 113 00:07:51,530 --> 00:07:57,200 But over here, let's take a moment to think about the base case as well for this recursive solution. 114 00:07:57,200 --> 00:08:04,100 Now we have decided in this case to go from zero to n, but we could have gone from N to zero as well. 115 00:08:04,100 --> 00:08:09,050 For the sake of this discussion, let's continue with the zero to n approach. 116 00:08:09,050 --> 00:08:12,650 So initially we start with the element at index zero. 117 00:08:12,650 --> 00:08:15,350 Then we proceed to the element at index one. 118 00:08:15,350 --> 00:08:19,940 And this keeps happening till we reach the last index over here. 119 00:08:19,940 --> 00:08:28,010 So if the length of this array over here is equal to n, then if we reach the value for the pointer 120 00:08:28,010 --> 00:08:35,480 which is used to iterate over all the valid indices, if that value reaches a value greater than n minus 121 00:08:35,480 --> 00:08:40,100 one, we would have encountered our first invalid input. 122 00:08:40,100 --> 00:08:45,500 Now again taking a moment over here, this n over here, let's say it's the length of the input array. 123 00:08:45,500 --> 00:08:51,740 And in general when we were saying zero to n, this n indicated the last valid index. 124 00:08:55,690 --> 00:09:03,190 So in this case this would be zero to n minus one because n minus one is the last valid index. 125 00:09:03,190 --> 00:09:11,080 So if the iterator gets a value which is greater than n minus one, we have hit our first invalid input. 126 00:09:11,080 --> 00:09:19,570 And in this case we can just return zero because if there are no valid elements, we cannot form any 127 00:09:19,570 --> 00:09:26,140 increasing subsequence and the length of a non existent subsequence is just zero. 128 00:09:26,140 --> 00:09:28,240 So that's why we can return zero over here. 129 00:09:28,330 --> 00:09:35,530 So we have built a first level understanding for implementing the recursive solution. 130 00:09:35,530 --> 00:09:41,110 For the Alice question, we have discussed what the choice diagram would be, as well as what the base 131 00:09:41,110 --> 00:09:42,010 condition is. 132 00:09:42,010 --> 00:09:48,910 We have also developed an intuition why the choice diagram actually works, and why by just going over 133 00:09:48,910 --> 00:09:55,930 the elements of the array and either excluding or including elements, we will be able to get all the 134 00:09:55,930 --> 00:09:57,400 possible subsequences. 135 00:09:57,400 --> 00:10:03,610 And we have also discussed what conditions are to be checked before we decide to include an element 136 00:10:03,610 --> 00:10:05,140 into a subsequence. 137 00:10:05,140 --> 00:10:10,300 Now in the next video, let's go ahead and draw the recursion tree of this approach. 138 00:10:10,300 --> 00:10:15,820 And once we are done with this, we will have a thorough understanding and we will be able to easily 139 00:10:15,820 --> 00:10:17,980 implement the code of this solution.