1 00:00:00,470 --> 00:00:01,610 Welcome back. 2 00:00:01,790 --> 00:00:09,230 To start with, let's make a few observations to develop the necessary intuition for solving this question. 3 00:00:09,230 --> 00:00:13,700 And for this, let's make use of the example which is given to us. 4 00:00:13,700 --> 00:00:20,090 So if there are three elements in the cost array which is given to us, and if the costs are one, two 5 00:00:20,090 --> 00:00:26,090 and three, we have seen that the expected output is two, because the best path or the path which involves 6 00:00:26,090 --> 00:00:32,780 the minimum cost for reaching the destination, is by starting at the step with index one and then taking 7 00:00:32,810 --> 00:00:35,600 two steps to reach the top or the destination. 8 00:00:35,600 --> 00:00:41,540 Now notice that over here the destination is beyond the given array. 9 00:00:41,540 --> 00:00:43,730 So this is an important thing to note over here. 10 00:00:43,730 --> 00:00:49,520 And that's why it's very important to take a look at the examples given along with the question when 11 00:00:49,520 --> 00:00:51,380 you are dealing with a coding interview question. 12 00:00:51,380 --> 00:00:56,360 So the examples given are always very helpful and very important. 13 00:00:56,360 --> 00:01:02,090 So the first observation that we have made over here is that the destination is beyond the given array. 14 00:01:02,090 --> 00:01:06,800 So we don't just need to reach this index we need to reach beyond it. 15 00:01:06,800 --> 00:01:13,370 The second thing that we can observe in this question is that it's mentioned that we have to pay to 16 00:01:13,370 --> 00:01:14,960 use a step, okay. 17 00:01:14,960 --> 00:01:18,230 So if I want to use this step I have to pay. 18 00:01:18,230 --> 00:01:23,300 And if I do pay, I can either take two steps or I can take one step. 19 00:01:23,300 --> 00:01:23,810 All right. 20 00:01:23,810 --> 00:01:28,640 So these are the important things to note or observe in this question before you go ahead and solve 21 00:01:28,640 --> 00:01:28,730 it. 22 00:01:28,730 --> 00:01:34,130 Because if you don't do that you will end up writing something which is not what the question demands 23 00:01:34,130 --> 00:01:34,790 from us. 24 00:01:35,000 --> 00:01:41,840 Now, to solve this question, first let's write the recursive approach, and then we will memorize 25 00:01:41,840 --> 00:01:44,690 it by just adding a few lines of code. 26 00:01:44,690 --> 00:01:48,680 And after this let's write the bottom up or tabulation approach. 27 00:01:48,680 --> 00:01:51,620 So let's get started with the recursive approach. 28 00:01:51,740 --> 00:01:58,520 And for discussing this approach, let's take the example where the cost array is one, two and three. 29 00:01:58,520 --> 00:02:00,950 So the indices are zero, one and two. 30 00:02:00,950 --> 00:02:05,510 And we will be writing a function which we will be recursively calling. 31 00:02:05,510 --> 00:02:12,620 So let's call this function cost from and to this function we will be passing the index as an input 32 00:02:12,620 --> 00:02:13,370 parameter. 33 00:02:13,370 --> 00:02:20,600 Now before we write this function, let's take a moment to discuss what this function actually will 34 00:02:20,600 --> 00:02:21,230 return. 35 00:02:21,230 --> 00:02:30,620 So cost from this particular index over here will return the cost of reaching the top from this particular 36 00:02:30,620 --> 00:02:31,190 index. 37 00:02:31,190 --> 00:02:34,400 Now again over here we are writing the recursive approach. 38 00:02:34,400 --> 00:02:40,970 And you can write recursive solutions either going from index zero to the last index. 39 00:02:40,970 --> 00:02:44,420 Or you can go from the last index to zero. 40 00:02:45,290 --> 00:02:46,040 Now over here. 41 00:02:46,040 --> 00:02:50,600 Let's go ahead and discuss this approach where we are starting at index zero. 42 00:02:50,600 --> 00:02:52,670 And we will be going to the last index. 43 00:02:52,670 --> 00:02:57,050 But it's always good for you to practice and write both the approaches. 44 00:02:57,050 --> 00:03:01,100 So let's just continue with the approach where we are starting at index zero. 45 00:03:01,100 --> 00:03:10,760 And in this context, cost from index will return the cost of reaching the top from the index at hand. 46 00:03:10,760 --> 00:03:14,540 So this is the definition of the cost from function. 47 00:03:14,540 --> 00:03:22,490 And after we have written this function, we would just have to finally return the minimum between cost 48 00:03:22,490 --> 00:03:24,950 from zero and cost from one. 49 00:03:24,950 --> 00:03:31,580 Because in the question it's mentioned that we can either start from the step with index zero or the 50 00:03:31,580 --> 00:03:32,900 step with index one. 51 00:03:32,900 --> 00:03:39,320 So if we start at the step with index zero, then we will call cost from zero. 52 00:03:39,320 --> 00:03:47,300 So this over here will return the minimum cost for reaching the top starting at the step with index 53 00:03:47,300 --> 00:03:47,810 zero. 54 00:03:47,810 --> 00:03:49,610 And again this is the minimum cost. 55 00:03:50,320 --> 00:03:58,930 Okay and cost from one will return the minimum cost for reaching the top when we start at the step with 56 00:03:58,930 --> 00:03:59,680 index one. 57 00:03:59,680 --> 00:04:03,280 So this is how we are going to implement the recursive function. 58 00:04:03,280 --> 00:04:07,780 Now let's discuss how this function over here can be written. 59 00:04:08,440 --> 00:04:10,840 Now again let's make some space over here. 60 00:04:10,840 --> 00:04:16,150 And we have seen that we will finally call cost from zero and cost from one. 61 00:04:16,150 --> 00:04:21,640 And the recursive tree for these two will follow a similar logical approach. 62 00:04:21,640 --> 00:04:28,300 So for our learning purpose, let's just write this recursive tree over here, which is cost from index 63 00:04:28,300 --> 00:04:28,900 zero. 64 00:04:28,900 --> 00:04:35,110 Now this over here means that we are starting at the step with index zero. 65 00:04:35,110 --> 00:04:42,430 Now we know that when we start at a particular step, we can take two possible approaches, which is 66 00:04:42,430 --> 00:04:46,480 that we can either take one step or we can take two steps. 67 00:04:46,480 --> 00:04:52,060 But in either of these cases, we are using this particular step over here. 68 00:04:52,060 --> 00:04:57,640 And remember in the question it's mentioned that whenever we use a step we have to pay for it. 69 00:04:57,640 --> 00:04:58,030 Right. 70 00:04:58,030 --> 00:05:03,580 And over here the cost for the step at index zero is equal to one. 71 00:05:03,580 --> 00:05:07,480 So that's why we'll have to pay one in either of these cases. 72 00:05:07,480 --> 00:05:11,440 So in either of these cases I will have to add one. 73 00:05:11,440 --> 00:05:17,740 And over here if I'm taking just one step when I'm starting from index zero, I would reach the step 74 00:05:17,740 --> 00:05:18,850 with index one. 75 00:05:18,850 --> 00:05:26,410 And then I would have to add to this one over here the cost for reaching the top starting at index one. 76 00:05:26,410 --> 00:05:33,220 So for that I would recursively call the cost from function again and pass one as the input parameter. 77 00:05:33,220 --> 00:05:39,250 And in this case, if I'm taking two steps and I'm starting at the step with index zero. 78 00:05:39,250 --> 00:05:44,350 So when I take two steps I will reach the step with index two and two. 79 00:05:44,380 --> 00:05:51,340 This one over here I'll have to add the cost for reaching the top starting at the step with index two, 80 00:05:51,370 --> 00:05:57,370 which can be obtained by recursively calling the cost from function and passing two to this function 81 00:05:57,370 --> 00:05:57,880 over here. 82 00:05:57,880 --> 00:06:02,500 So these are the two branches that the recursive algorithm will take. 83 00:06:02,500 --> 00:06:04,780 And then it will just go on in this manner. 84 00:06:04,780 --> 00:06:05,080 Right. 85 00:06:05,080 --> 00:06:07,990 So over here again we would use this particular step. 86 00:06:07,990 --> 00:06:09,520 And there would be two branches. 87 00:06:09,520 --> 00:06:13,780 The branch where we take one step and the branch where we take two steps. 88 00:06:13,780 --> 00:06:15,550 And it goes on in this manner. 89 00:06:15,550 --> 00:06:17,440 So I think this is pretty straightforward. 90 00:06:17,440 --> 00:06:21,340 And there's no need for us to draw the complete recursion tree. 91 00:06:21,340 --> 00:06:23,950 So this is the recursive case. 92 00:06:23,950 --> 00:06:28,480 Now let's also discuss the base case for the recursive solution. 93 00:06:28,480 --> 00:06:30,400 So what would be the base case. 94 00:06:30,400 --> 00:06:36,670 Now always remember the base case will vary depending on whether you're going from zero to the last 95 00:06:36,670 --> 00:06:42,190 index, or whether you are writing the solution in a way that you're starting at the last index and 96 00:06:42,190 --> 00:06:43,180 going to zero. 97 00:06:43,180 --> 00:06:49,660 So in this case, because we are going from zero to the last index, we would hit the base case or the 98 00:06:49,660 --> 00:06:56,740 terminating case when the index that we are passing to the cost from function is beyond the last valid 99 00:06:56,740 --> 00:06:57,280 index. 100 00:06:57,280 --> 00:07:03,610 So in this case the last valid index is n minus one, where n is the length of the cost array. 101 00:07:03,610 --> 00:07:09,850 So if the index is greater than n minus one, we know that we can stop. 102 00:07:09,850 --> 00:07:12,670 And at that point we can just return zero. 103 00:07:12,670 --> 00:07:18,670 Now the reason why we can return zero is that because we have reached beyond the last index. 104 00:07:18,670 --> 00:07:23,530 And remember we had discussed that our destination is beyond the last index. 105 00:07:23,530 --> 00:07:29,260 So if the index is greater than n minus one, it would mean that we have already reached the destination. 106 00:07:29,260 --> 00:07:31,600 And that's why the cost would be zero. 107 00:07:31,600 --> 00:07:36,580 And that is the reason why we can return zero if index is greater than n minus one. 108 00:07:36,580 --> 00:07:40,090 So this is the recursive approach for solving this question. 109 00:07:40,090 --> 00:07:44,410 We have discussed both the recursive case as well as the base case. 110 00:07:44,440 --> 00:07:51,160 Now all that remains is to discuss the complexity, the time and space complexity of this approach, 111 00:07:51,160 --> 00:07:55,120 as well as to implement the code of this approach. 112 00:07:55,120 --> 00:07:57,940 Let's do that in the upcoming videos.