1 00:00:00,540 --> 00:00:01,650 Welcome back. 2 00:00:01,650 --> 00:00:05,310 Let's now get into the approach for solving this question. 3 00:00:05,310 --> 00:00:13,620 Now the jump game question can be solved both using dynamic programming as well as the greedy approach. 4 00:00:13,620 --> 00:00:16,650 And we will soon discuss why this is the case. 5 00:00:16,650 --> 00:00:22,920 But remember, whenever you have a question that can be solved both using dynamic programming as well 6 00:00:22,920 --> 00:00:28,950 as the greedy approach, typically the greedy approach will give you a better time complexity. 7 00:00:28,950 --> 00:00:31,500 Now let's get into the nitty gritties. 8 00:00:31,500 --> 00:00:36,000 Why is it that this question can be solved with dynamic programming? 9 00:00:36,000 --> 00:00:39,000 Now for discussing this, let's take an example. 10 00:00:39,000 --> 00:00:45,000 Let's say the array which is given to us is this array over here, which is 23104. 11 00:00:45,000 --> 00:00:48,990 And let me write the indices which go from zero up to four. 12 00:00:48,990 --> 00:00:51,330 Now we start at index zero. 13 00:00:51,330 --> 00:00:58,470 And because the value over here is two, it means that I can make a jump of up to two indices. 14 00:00:58,470 --> 00:00:58,830 Okay. 15 00:00:58,830 --> 00:01:02,280 So I can go from here to here or from here to here. 16 00:01:02,280 --> 00:01:07,020 So these are the two places that I can reach from this index over here. 17 00:01:07,020 --> 00:01:10,590 So notice choices are involved over here. 18 00:01:10,590 --> 00:01:16,800 I can either choose to come to this place or I can choose to come to this place over here. 19 00:01:16,800 --> 00:01:24,210 And when we discuss dynamic programming, this was one of the hints that indicate that probably we can 20 00:01:24,210 --> 00:01:25,800 use dynamic programming. 21 00:01:25,800 --> 00:01:28,770 Now there is another interesting thing that we can see over here. 22 00:01:28,770 --> 00:01:30,660 We start at index zero. 23 00:01:30,660 --> 00:01:34,500 And if I make a jump of one unit, I reach index one. 24 00:01:34,500 --> 00:01:38,670 And if I take a jump of two units, I reach index two. 25 00:01:38,670 --> 00:01:39,150 Okay. 26 00:01:39,150 --> 00:01:42,420 And notice we are having branches over here. 27 00:01:42,420 --> 00:01:48,270 This is another interesting hint that we discussed in dynamic programming, because whenever you have 28 00:01:48,270 --> 00:01:53,280 branches like this, there is a high chance for overlapping subproblems. 29 00:01:53,280 --> 00:02:00,480 Now again, just to take this a little bit deeper from index one, we can either take a jump of one, 30 00:02:00,480 --> 00:02:01,320 2 or 3. 31 00:02:01,320 --> 00:02:01,650 Okay. 32 00:02:01,650 --> 00:02:05,910 So that means I can reach indices two, 3 or 4. 33 00:02:05,910 --> 00:02:07,650 So these would be the branches. 34 00:02:07,650 --> 00:02:10,290 And notice we have two over here. 35 00:02:10,290 --> 00:02:15,720 And we have two over here which indicates the presence of overlapping subproblems. 36 00:02:15,720 --> 00:02:23,040 And again remember this over here represents whether we can reach the last index starting at index two. 37 00:02:23,040 --> 00:02:25,080 So that's the subproblem over here. 38 00:02:25,080 --> 00:02:27,270 And that's the same thing that we have over here. 39 00:02:27,270 --> 00:02:31,560 Whether we can reach the last index starting at index two. 40 00:02:31,590 --> 00:02:34,290 So we have overlapping subproblems. 41 00:02:34,290 --> 00:02:36,360 We have branches we have choices. 42 00:02:36,360 --> 00:02:42,180 And all of this indicates that probably we can use dynamic programming to solve this question. 43 00:02:42,180 --> 00:02:47,190 Also notice that this question has optimal substructure. 44 00:02:47,190 --> 00:02:54,870 And with that I mean that we can use solutions to subproblems to identify the solution for the original 45 00:02:54,870 --> 00:02:55,530 problem. 46 00:02:55,530 --> 00:02:55,980 Again. 47 00:02:55,980 --> 00:03:02,850 For example, notice a subproblem could be whether you can go to index four from index two okay. 48 00:03:02,850 --> 00:03:04,230 That's what we had over here. 49 00:03:04,320 --> 00:03:08,400 And we can use these to identify the solution to the problem okay. 50 00:03:08,400 --> 00:03:15,690 Another example would be if I know the answer to the subproblem which is that I can go from 1 to 4 okay. 51 00:03:15,690 --> 00:03:21,180 And I can do that because I can just take a jump of three units so I can go from 1 to 4. 52 00:03:21,180 --> 00:03:28,110 So knowing this subproblem okay, which is this over here helps me solve the original problem, which 53 00:03:28,110 --> 00:03:31,920 is whether I can go from 0 to 4, which is what we have over here. 54 00:03:31,920 --> 00:03:39,060 And again, notice I can go from 0 to 4 if I can go from 1 to 4, because I can just go from 0 to 1. 55 00:03:39,060 --> 00:03:40,440 That's also possible, right? 56 00:03:40,440 --> 00:03:46,860 So again, notice knowing the solution to subproblems helps me identify the solution to the original 57 00:03:46,860 --> 00:03:47,790 problem at hand. 58 00:03:47,790 --> 00:03:51,240 And therefore this question has optimal substructure. 59 00:03:51,240 --> 00:03:56,100 And we have already seen that there is a high chance that it has overlapping subproblems. 60 00:03:56,100 --> 00:04:00,120 And in fact, we did validate that there are overlapping subproblems. 61 00:04:00,120 --> 00:04:04,950 And for these reasons, we can use dynamic programming to solve this question. 62 00:04:04,950 --> 00:04:06,540 Now a quick side note. 63 00:04:06,540 --> 00:04:12,060 Okay, we will not be covering the dynamic programming approach in detail in this video, but we'll 64 00:04:12,060 --> 00:04:13,920 just build the approach over here. 65 00:04:13,920 --> 00:04:20,250 And I'll give you a separate article in this section where the dynamic programming solutions will be 66 00:04:20,250 --> 00:04:20,850 mentioned. 67 00:04:20,850 --> 00:04:21,450 All right. 68 00:04:21,480 --> 00:04:26,790 Now let's take the example where the array which is given to us is 23104 okay. 69 00:04:26,790 --> 00:04:30,360 And the indices start from zero and go up to four. 70 00:04:30,360 --> 00:04:36,210 Now if I were to draw the recursive tree over here and again, remember whenever you start with dynamic 71 00:04:36,210 --> 00:04:41,880 programming and when you're dealing with a new type of question, always first come up with the recursive 72 00:04:41,880 --> 00:04:47,730 solution, then memorize it, and then you will be in a position to even write the tabulation approach. 73 00:04:47,730 --> 00:04:52,620 So if we take a look at the recursive tree over here, I'm starting at index zero. 74 00:04:52,620 --> 00:04:55,680 And from zero I can get to index 1 or 2. 75 00:04:55,680 --> 00:04:59,520 And from index one I can get to index two, three and four. 76 00:04:59,710 --> 00:05:01,390 We have already discussed that previously. 77 00:05:01,420 --> 00:05:08,470 Now notice what's actually happening over here is that we are following a backtracking or a recursive 78 00:05:08,470 --> 00:05:09,340 approach over here. 79 00:05:09,340 --> 00:05:14,320 And again, it's not typically backtracking in the technical sense where we are making changes to the 80 00:05:14,320 --> 00:05:19,540 state of the problem in place, but rather technically it's just a recursive approach where we will 81 00:05:19,540 --> 00:05:26,650 be exploring all the different paths possible until we either get true or we have explored all the possible 82 00:05:26,650 --> 00:05:28,570 paths and we see that it's not possible. 83 00:05:28,570 --> 00:05:28,900 Right? 84 00:05:28,900 --> 00:05:32,290 So this would be the recursive way of solving this question. 85 00:05:32,290 --> 00:05:36,250 And then you can memorize this by just having a DP table. 86 00:05:36,250 --> 00:05:38,590 So over here you have five elements. 87 00:05:38,590 --> 00:05:41,920 So in the DP table you will also need five cells. 88 00:05:41,920 --> 00:05:45,160 And you will fill every cell with either true or false. 89 00:05:45,160 --> 00:05:47,650 And again what would each cell represent. 90 00:05:47,650 --> 00:05:54,460 For example this cell over here would represent whether you can get to the last index from this cell. 91 00:05:54,460 --> 00:05:57,430 So if you can do that we will fill true over here. 92 00:05:57,430 --> 00:06:00,280 Otherwise we'll have the value false over here okay. 93 00:06:00,280 --> 00:06:02,230 So this is how you can memorize this. 94 00:06:02,230 --> 00:06:08,680 And if you can write the memoization solution for this problem you can definitely write the tabulation 95 00:06:08,680 --> 00:06:11,500 approach or the bottom up approach as well. 96 00:06:11,500 --> 00:06:11,860 Okay. 97 00:06:11,860 --> 00:06:16,450 Now again as I've mentioned, we are not going to discuss this in detail over here because we are dealing 98 00:06:16,450 --> 00:06:17,530 with the greedy approach. 99 00:06:17,530 --> 00:06:22,300 But I will provide you an article with the dynamic programming solutions as well. 100 00:06:22,300 --> 00:06:22,960 All right. 101 00:06:22,960 --> 00:06:24,250 So let's get back. 102 00:06:24,250 --> 00:06:29,260 We have seen that we can solve the jump game question using dynamic programming. 103 00:06:29,260 --> 00:06:34,690 Now let's discuss why we can solve this question using the greedy algorithm. 104 00:06:34,690 --> 00:06:41,350 First of all notice this is an optimization problem because we have discussed that the greedy approach 105 00:06:41,350 --> 00:06:44,260 is used for solving optimization questions. 106 00:06:44,260 --> 00:06:47,110 Now how is this an optimization question? 107 00:06:47,110 --> 00:06:50,980 We are just trying to see whether you can get to the last index. 108 00:06:50,980 --> 00:06:55,960 When you start at the first index, how come this is an optimization problem, right. 109 00:06:55,960 --> 00:07:04,420 So again you can think of this as maximizing the reach within the constraints provided by the elements 110 00:07:04,420 --> 00:07:05,590 of the array okay. 111 00:07:05,590 --> 00:07:11,020 And again with maximizing the reach we mean whether you can reach this position or not. 112 00:07:11,020 --> 00:07:17,980 And the constraints provided by the elements of the array is the value in the array at each position 113 00:07:17,980 --> 00:07:18,220 okay. 114 00:07:18,220 --> 00:07:21,730 Because that determines the number of positions you can jump. 115 00:07:21,730 --> 00:07:24,790 So that's why this is an optimization problem. 116 00:07:24,790 --> 00:07:25,540 All right. 117 00:07:25,540 --> 00:07:27,640 So this is an optimization question. 118 00:07:27,640 --> 00:07:30,670 Now what else is there that can help us identify that. 119 00:07:30,670 --> 00:07:34,390 This is a question that can be solved using the greedy algorithm. 120 00:07:34,390 --> 00:07:35,560 Let's think about that. 121 00:07:35,560 --> 00:07:42,550 So the next thing that helps us identify this as a question that can be solved using the greedy algorithm, 122 00:07:42,550 --> 00:07:47,350 is the fact that this problem follows the greedy choice property. 123 00:07:47,350 --> 00:07:49,210 And again, why is that the case? 124 00:07:49,210 --> 00:07:57,070 This is the case because making locally optimal solutions will help us arrive at the global optimal 125 00:07:57,070 --> 00:07:59,920 solution, which is to identify true or false. 126 00:07:59,920 --> 00:08:00,370 Okay. 127 00:08:00,370 --> 00:08:05,770 And again we're just trying to understand whether we can reach at the last index starting at the first 128 00:08:05,770 --> 00:08:06,340 index. 129 00:08:06,340 --> 00:08:12,820 Now what is the locally optimal choice or the greedy choice that we will be making at every index? 130 00:08:12,820 --> 00:08:20,920 The thing that we will be doing is to jump to the farthest reachable index from each reachable index. 131 00:08:20,920 --> 00:08:26,500 We will soon discuss this in detail when we discuss the greedy approach for solving this question. 132 00:08:26,500 --> 00:08:31,870 Now, if this is not clear to you, let's just assume that this is true because this will soon become 133 00:08:31,870 --> 00:08:35,500 clear to you in the next video when we discuss this in detail. 134 00:08:35,500 --> 00:08:41,620 But because this is true, and we are just assuming this to be true at this point, the question follows 135 00:08:41,620 --> 00:08:43,060 the greedy choice property. 136 00:08:43,060 --> 00:08:49,360 And this also helps us understand that this is a question that can be solved using the greedy algorithm. 137 00:08:49,360 --> 00:08:49,900 All right. 138 00:08:49,900 --> 00:08:56,650 In the next two videos, let's discuss two greedy approaches that we can use, which are pretty similar, 139 00:08:56,650 --> 00:09:01,750 with the only difference that in one case we will be going from the beginning to the end, and the other 140 00:09:01,750 --> 00:09:04,750 case we will be going from the ending of the array to the beginning. 141 00:09:04,750 --> 00:09:08,980 Okay, so let's discuss two greedy approaches for solving this question.