1 00:00:01,589 --> 00:00:02,260 Hi, everyone. 2 00:00:02,280 --> 00:00:08,220 So in this video, also, we are discussing the question of minimum steps to one, but in this video 3 00:00:08,220 --> 00:00:11,370 we will implement the bottom of the creative solution. 4 00:00:12,570 --> 00:00:16,410 So in the last video, what we did, we created an Eddie. 5 00:00:17,700 --> 00:00:24,600 The name of that, it was on set and the size of that it was and Blessin and I initialised David minus 6 00:00:24,600 --> 00:00:25,260 one initially. 7 00:00:26,510 --> 00:00:32,240 Then I told you my answer was this one, so this is the last index my -- will represented. 8 00:00:32,540 --> 00:00:34,490 Now what will happen for calculating? 9 00:00:34,490 --> 00:00:37,700 And so just like Fibonacci, for calculating and what it will do? 10 00:00:37,700 --> 00:00:39,800 So in the worst case, there will be three calls. 11 00:00:40,010 --> 00:00:42,530 So it will call on and minus one it will call on. 12 00:00:42,920 --> 00:00:45,540 And by two, it will also call an end by three. 13 00:00:46,460 --> 00:00:49,180 Similarly again, what will happen? 14 00:00:49,190 --> 00:00:52,640 So for calculating and minus one, it will again call on and minus two. 15 00:00:52,670 --> 00:00:54,230 So again, half. 16 00:00:54,230 --> 00:00:55,580 And then again one third. 17 00:00:55,850 --> 00:00:56,880 So this will go on. 18 00:00:57,200 --> 00:00:58,830 And finally, what will happen? 19 00:00:58,850 --> 00:01:00,290 So we will hit the Biscuit's. 20 00:01:00,290 --> 00:01:02,110 So 011 they are the best case. 21 00:01:02,120 --> 00:01:03,350 They both are containing zeros. 22 00:01:03,590 --> 00:01:07,000 So finally I will reach here and then I will fill this position. 23 00:01:07,280 --> 00:01:09,340 Then next position will be filled. 24 00:01:09,350 --> 00:01:12,280 Then the next position will be filled, the next position will be filled. 25 00:01:12,560 --> 00:01:13,860 Then this position will be filled. 26 00:01:14,030 --> 00:01:16,700 And then finally this position will be filled. 27 00:01:16,700 --> 00:01:18,080 And we will then I would answer. 28 00:01:18,560 --> 00:01:24,050 So again, just like in Fibonacci, what we are doing, we are first reversing in this direction, then 29 00:01:24,050 --> 00:01:26,870 we are filling the area while we are moving in this direction. 30 00:01:27,320 --> 00:01:30,920 So what we can do, we can avoid moving in this direction. 31 00:01:31,460 --> 00:01:34,490 We can directly move in this direction and can fill that. 32 00:01:35,150 --> 00:01:37,610 OK, so what we will do, we will create again. 33 00:01:37,840 --> 00:01:41,110 So for Bottom-Up DEPI, again, we have to create our area. 34 00:01:41,360 --> 00:01:43,930 So what I will do, I will create an area. 35 00:01:44,480 --> 00:01:47,500 So let's say this time I'm naming the area, Deepti. 36 00:01:47,980 --> 00:01:48,330 OK. 37 00:01:48,350 --> 00:01:50,520 So again, the size will be in plus one. 38 00:01:51,050 --> 00:01:55,120 So what we have to do since we are, we will fill that in this direction. 39 00:01:55,130 --> 00:01:57,080 I will initialize my 021 index. 40 00:01:57,410 --> 00:02:02,780 So if you are standing at one M. steps required at zero and four zero zero zero. 41 00:02:03,750 --> 00:02:05,820 So this is the net position. 42 00:02:06,380 --> 00:02:09,509 OK, so what we will do, this is the eighth position. 43 00:02:10,930 --> 00:02:14,750 So what is BP, what does Deepthi contains? 44 00:02:15,160 --> 00:02:22,030 So this is BP office or BP a I mean, minimum steps required to move from eye to one. 45 00:02:22,390 --> 00:02:28,100 So this is the meaning of BP of a minimum steps required to move from position to position. 46 00:02:28,930 --> 00:02:35,890 So what is deep and so deep and contains the steps required from moving the position and to one? 47 00:02:36,880 --> 00:02:37,980 What will my answer? 48 00:02:38,230 --> 00:02:40,510 My answer will be BP often. 49 00:02:41,110 --> 00:02:42,870 So this will be my answer. 50 00:02:43,090 --> 00:02:49,360 So I'm repeating myself, despite the meaning of the fire, is basically minimum steps required to move 51 00:02:49,360 --> 00:02:50,370 from to one. 52 00:02:51,070 --> 00:02:55,720 So that means DPF and next steps required to move from nine to one. 53 00:02:56,200 --> 00:02:57,700 And that is my answer. 54 00:02:57,910 --> 00:03:00,100 OK, so this position will be my answer. 55 00:03:01,180 --> 00:03:03,150 Now what is Deepthi? 56 00:03:04,210 --> 00:03:07,320 How can we flip your face or typify what it will do? 57 00:03:07,660 --> 00:03:11,600 So there are three options available, so I will take the minimum of three options. 58 00:03:11,830 --> 00:03:14,770 So first one is deep of i.e. minus one. 59 00:03:15,400 --> 00:03:23,410 The second option is deep of I bitou and also we will check if I am or two is zero and the third is 60 00:03:23,410 --> 00:03:24,860 basically deep off. 61 00:03:24,880 --> 00:03:26,650 I buy three again. 62 00:03:26,650 --> 00:03:27,400 We have to check. 63 00:03:28,060 --> 00:03:31,870 So we will take the minimum of these three and I will add plus one. 64 00:03:32,320 --> 00:03:32,810 Simple. 65 00:03:33,070 --> 00:03:35,710 So you want to calculate Deepthi what you will do. 66 00:03:36,040 --> 00:03:37,780 Golon Deepthi minus one. 67 00:03:39,280 --> 00:03:49,420 Collen, deep of battle and colon deep, DPF so deep I buy three, take the minimum of these three and 68 00:03:49,420 --> 00:03:51,940 obviously since you took one jump to reach there. 69 00:03:52,210 --> 00:03:53,950 So that's why you will add plus one. 70 00:03:55,190 --> 00:03:57,240 OK, so very, very simple. 71 00:03:57,890 --> 00:04:00,680 So now let us implement the bottom of DP. 72 00:04:08,880 --> 00:04:12,250 So let's say that there will always be a.. 73 00:04:12,630 --> 00:04:18,620 Obviously, it will be easier, so the name of the function is minimum steps three it will take and 74 00:04:18,630 --> 00:04:20,880 as input now what we have to do. 75 00:04:23,860 --> 00:04:30,490 So I have to create an idea first, so instead, let's name BP, because at many places you will see 76 00:04:30,490 --> 00:04:31,710 the name of that is DPE. 77 00:04:32,340 --> 00:04:36,310 OK, so many people use Dippin, so let's name their DP. 78 00:04:37,510 --> 00:04:40,540 And the size of the is basically and plus one. 79 00:04:42,890 --> 00:04:46,580 Now, what they have to do, so you have to initialize the base case, so here. 80 00:04:47,700 --> 00:04:57,030 So basically, so what will do will initialised the 010 first position, so DPF zero is zero and DEPI. 81 00:04:58,620 --> 00:05:00,700 Often is one. 82 00:05:02,480 --> 00:05:04,430 So what does 80 percent. 83 00:05:07,200 --> 00:05:13,290 So I'm reading it here so that you can understand sort of I present the minimum steps. 84 00:05:16,030 --> 00:05:16,570 Needed. 85 00:05:17,580 --> 00:05:18,270 To move. 86 00:05:24,050 --> 00:05:30,550 To move from I to one, so that means going by this definition. 87 00:05:30,560 --> 00:05:35,270 So that means my answer should be DEPI often simple. 88 00:05:36,300 --> 00:05:38,270 OK, so now we have to fill this out. 89 00:05:39,020 --> 00:05:40,810 So now let us fill this area. 90 00:05:41,940 --> 00:05:48,900 So I will start feeling from two because 091 these indexes have already been filled and obviously I 91 00:05:48,900 --> 00:05:53,520 have to go in and I placeless, then what will do? 92 00:05:53,970 --> 00:05:56,030 So again, we have to copy this code. 93 00:05:56,160 --> 00:05:59,340 We will do very similar to copy this code. 94 00:06:03,050 --> 00:06:06,200 So, Pastor Ted, now, what are the changes that we have to do? 95 00:06:08,920 --> 00:06:10,810 So obviously, we need expert. 96 00:06:12,200 --> 00:06:13,700 We do not have to call any function. 97 00:06:13,880 --> 00:06:20,300 All right, so is basically the first option, five minus one, Y and Z, Y and Z will be initialized 98 00:06:20,300 --> 00:06:22,190 with in the maximum. 99 00:06:31,490 --> 00:06:32,750 Then what we have to do so. 100 00:06:35,010 --> 00:06:41,550 I have to check, so if I go back to what is way, so why is nothing, it is just a of faith and by 101 00:06:41,550 --> 00:06:44,220 doing so this is DBF and BITOU. 102 00:06:45,780 --> 00:06:47,790 And similarly, I will check for a. 103 00:06:49,210 --> 00:06:55,690 So if I is little bit, then it will be deep of inventory. 104 00:07:02,380 --> 00:07:04,360 Sort of arbitrary, not an. 105 00:07:09,320 --> 00:07:11,320 OK, so we are constructing a very. 106 00:07:12,660 --> 00:07:19,140 This is the best case then, despite the definition, is Muno steps required to move from to so going 107 00:07:19,140 --> 00:07:22,290 by definition, Dancer will be present at DEPI often. 108 00:07:23,290 --> 00:07:29,860 So now I am feeling the are starting from tootle in shapelessness, so first option X, Y, minus one 109 00:07:29,860 --> 00:07:34,670 Y and Z Visored and A more to zero, five by five by three. 110 00:07:34,990 --> 00:07:40,300 And finally, what you can do, you can return your answer, which is DPF and. 111 00:07:41,530 --> 00:07:42,100 Simple. 112 00:07:43,240 --> 00:07:45,250 So now let's call this function. 113 00:07:48,270 --> 00:07:49,170 So out. 114 00:07:51,220 --> 00:07:55,300 Minimum steps three, and we will pass an. 115 00:07:56,580 --> 00:08:02,220 And OK, so I think we did everything fine, so let's test our on. 116 00:08:07,370 --> 00:08:09,350 OK, so this is minimum steps three. 117 00:08:15,600 --> 00:08:18,510 Now, let's say the value of N is, let's say 250. 118 00:08:21,890 --> 00:08:24,500 OK, so we did something we did something wrong. 119 00:08:24,530 --> 00:08:25,250 Let me check. 120 00:08:29,010 --> 00:08:30,330 So this will be zero. 121 00:08:31,820 --> 00:08:36,350 This individual, because if you are standing at one, then if you want to reach one, so the value 122 00:08:36,350 --> 00:08:36,890 will be zero. 123 00:08:36,929 --> 00:08:37,250 OK. 124 00:08:38,390 --> 00:08:40,159 Minimum steps required will be zero. 125 00:08:40,520 --> 00:08:45,770 So here we did zero, but here, I don't know how, but I write one. 126 00:08:45,770 --> 00:08:47,180 So sorry for that. 127 00:08:51,860 --> 00:08:53,090 So let's say 9:00 to 5:00. 128 00:08:55,110 --> 00:08:56,760 Again, zero strange. 129 00:08:58,750 --> 00:09:00,880 OK, so very huge mistake. 130 00:09:00,910 --> 00:09:04,900 So here what we are doing, we have to take a minimum and we have to add plus one. 131 00:09:04,900 --> 00:09:07,410 So I'm not doing this. 132 00:09:07,420 --> 00:09:09,130 So this is deep of a. 133 00:09:10,560 --> 00:09:12,690 What you have to do, we have to take so if you will see. 134 00:09:14,730 --> 00:09:20,070 So Depfa is actually we have to take the minimum minimum of these three and we have to add plus one, 135 00:09:20,070 --> 00:09:21,550 so I forgot to write this one. 136 00:09:21,570 --> 00:09:23,160 OK, I'm so sorry. 137 00:09:24,840 --> 00:09:33,330 Today's my bad luck, I think so I have to take a minimum of X, then again, minimum of Y and Z and 138 00:09:33,600 --> 00:09:34,140 plus one. 139 00:09:40,620 --> 00:09:42,940 Now, this time, Richard, voxel 95. 140 00:09:43,530 --> 00:09:46,770 Yes, so this is working, OK, our output is coming out. 141 00:09:46,810 --> 00:09:47,170 OK, great. 142 00:09:47,190 --> 00:09:49,430 So let's test it one more time. 143 00:09:52,480 --> 00:09:53,770 Now, let's say the value is. 144 00:09:55,430 --> 00:10:00,050 265, so, yes, it is working, OK, so our goal is working. 145 00:10:01,580 --> 00:10:04,200 Now, what is the time, complexity of this cold? 146 00:10:04,880 --> 00:10:10,880 So basically will see carefully what we are doing, we are just creating an area and we are simply activating. 147 00:10:11,210 --> 00:10:17,540 So the time complexity is big often and also the space complexity is big often because we are constructing 148 00:10:17,540 --> 00:10:17,980 this area. 149 00:10:18,320 --> 00:10:24,860 Now, one more thing, since I have used a dynamic location, so what we can do so before returning 150 00:10:24,860 --> 00:10:29,930 the answer, you can store the answer in a variable and then believe that and then return the answer. 151 00:10:29,960 --> 00:10:32,480 OK, so you have to delete the memory yourself. 152 00:10:32,510 --> 00:10:37,630 OK, so I forgot to delete and you can only tell yourself now one more thing. 153 00:10:38,510 --> 00:10:42,900 So if you are tired of writing X, Y, Z, so what you can do. 154 00:10:44,480 --> 00:10:48,020 So let me copy, let me comment on this called. 155 00:11:02,230 --> 00:11:06,040 So there's no need to create X, Y and Z variables, which you can do. 156 00:11:07,690 --> 00:11:11,710 The logic is the same, but the way of writing is different. 157 00:11:11,740 --> 00:11:12,510 So what will do? 158 00:11:13,540 --> 00:11:16,570 So I will write initially DPE of. 159 00:11:18,230 --> 00:11:24,770 I is actually DPF, I mean, this one, then here I will write the BofI. 160 00:11:26,000 --> 00:11:28,220 Is minimum of. 161 00:11:29,760 --> 00:11:31,470 The current value of a. 162 00:11:33,730 --> 00:11:34,960 And if I were to. 163 00:11:37,270 --> 00:11:40,840 And again, deep of I. 164 00:11:42,540 --> 00:11:46,920 Is minimum of Deepthi. 165 00:11:48,660 --> 00:11:50,010 And fire Batory. 166 00:11:53,800 --> 00:11:55,390 So this will be plus one. 167 00:11:58,650 --> 00:12:05,280 Again, DPL five by two plus one, five, three plus one, and then you can remove this line. 168 00:12:08,370 --> 00:12:13,270 OK, so the logic is the same, everything the same, but the way of writing the code is different. 169 00:12:14,070 --> 00:12:19,770 So initially I am initializing BofI with DPL five minus one, plus one, and then I'm taking a minimum 170 00:12:19,770 --> 00:12:20,040 here. 171 00:12:20,490 --> 00:12:26,040 If I little by two, then I'm taking the minimum of the current value that I have and I buy two plus 172 00:12:26,040 --> 00:12:26,220 one. 173 00:12:32,460 --> 00:12:40,320 And similarly, if I resolve it, then DPO five will be minimum of the current value of deeper and deeper 174 00:12:40,320 --> 00:12:41,400 if by three plus one. 175 00:12:41,670 --> 00:12:47,220 OK, so I have commented out this one old one and let's test this one also. 176 00:12:50,100 --> 00:12:57,480 The value is, let's say 85 and yes, our gold is working, so if you prefer this one approach X, Y, 177 00:12:57,480 --> 00:13:02,320 Z, you can use this one and if you can preffered this one approach so you can use this one. 178 00:13:03,360 --> 00:13:07,780 Both are correct and what you have to do here so you can do it yourself. 179 00:13:08,220 --> 00:13:11,430 So first you have to delete the idea that we have a look at it. 180 00:13:11,440 --> 00:13:12,900 OK, so delete the array. 181 00:13:13,620 --> 00:13:15,190 So let me do it for you. 182 00:13:15,210 --> 00:13:15,600 OK. 183 00:13:16,860 --> 00:13:21,180 So what you have to do, so first you will store your answer because you have to delete the. 184 00:13:23,110 --> 00:13:26,890 So let's take a variable answer, so the answer is deep in. 185 00:13:28,140 --> 00:13:30,690 Then you will do that, so delete keyword. 186 00:13:32,710 --> 00:13:36,520 The name of that is BP, and then you will return the answer. 187 00:13:38,420 --> 00:13:40,010 OK, so let's test. 188 00:13:43,350 --> 00:13:43,620 Well. 189 00:13:44,670 --> 00:13:46,500 So three, OK, so our court is looking. 190 00:13:48,280 --> 00:13:52,930 So if you have any doubt in these questions, you can ask me, I will see you in the next one by.