1
00:00:01,810 --> 00:00:02,450
Hello, everyone.

2
00:00:02,469 --> 00:00:08,109
So in this video, we'll discuss the question we know steps to one show in the last year days we implemented

3
00:00:08,160 --> 00:00:09,010
a solution.

4
00:00:09,190 --> 00:00:10,090
Now we will check.

5
00:00:10,330 --> 00:00:14,920
We will do there occasionally and we will check whether there is any repetition or recalculation.

6
00:00:15,130 --> 00:00:21,010
So if there is any repetition or recalculation, then we can use the memorization technique, the top

7
00:00:21,010 --> 00:00:21,250
down.

8
00:00:22,210 --> 00:00:22,950
So let's see.

9
00:00:23,260 --> 00:00:25,890
So let us take an example to the value of industrial.

10
00:00:26,680 --> 00:00:28,500
So 12 will call on 11.

11
00:00:29,020 --> 00:00:30,580
So tell us why do so?

12
00:00:30,580 --> 00:00:33,310
We can also call on six July three.

13
00:00:33,310 --> 00:00:35,970
So it will call for now for 11.

14
00:00:36,820 --> 00:00:40,000
Obviously I can call 11 is Nahdlatul by two.

15
00:00:40,000 --> 00:00:42,690
So no call 11 is Nahdlatul by three.

16
00:00:42,700 --> 00:00:43,660
So no call at all.

17
00:00:44,080 --> 00:00:44,620
Six.

18
00:00:45,010 --> 00:00:46,240
I will call on five.

19
00:00:46,810 --> 00:00:52,780
Six is Dugal by two so I will call on three and six is little by three so I will call on two forfour.

20
00:00:52,900 --> 00:00:54,010
I can call on three.

21
00:00:55,180 --> 00:01:01,120
For four voyages, so I will call on to four is not dizzle by three, so no call at all.

22
00:01:01,690 --> 00:01:06,610
Now 14 I will call on nine, I can also call and five.

23
00:01:07,810 --> 00:01:12,970
I cannot then is not a celebrity, so at done so for nine, I can call on it.

24
00:01:13,630 --> 00:01:17,320
So nine is not DL by two, so no goal line is DL by three.

25
00:01:17,320 --> 00:01:18,970
So there will be a call three.

26
00:01:20,090 --> 00:01:26,990
Four, eight, seven, eight is decided by two to four, then no collar at all, so for three, call

27
00:01:27,200 --> 00:01:33,290
two and then two is not easy by two and then three is decided by three.

28
00:01:33,290 --> 00:01:40,840
So it will be one and similarly four, then it will be no collar at all and no collar at all.

29
00:01:41,690 --> 00:01:43,690
And similarly, you can complete dedication.

30
00:01:43,730 --> 00:01:43,970
Three.

31
00:01:44,000 --> 00:01:45,980
OK, so it will continue to go on.

32
00:01:46,850 --> 00:01:48,650
Now let's see if there is any repetition.

33
00:01:49,490 --> 00:01:52,040
So for I am calculating for again.

34
00:01:52,940 --> 00:01:54,230
I'm calculating for.

35
00:01:55,290 --> 00:01:56,430
Again, I have four.

36
00:01:57,640 --> 00:02:06,850
Then similarly, I have five, five, similarly, we have three, three, three, then again two to

37
00:02:07,560 --> 00:02:07,880
two.

38
00:02:08,520 --> 00:02:13,020
So basically there is repetition and we are recalculating our answer again and again.

39
00:02:13,590 --> 00:02:16,980
Now, let us discuss the complexity of our recursion method.

40
00:02:17,340 --> 00:02:19,160
Now, in the worst case, what will happen?

41
00:02:19,290 --> 00:02:25,380
So each node will call on three nodes and minus one and my two and and rightly so, if we will blindly

42
00:02:25,380 --> 00:02:27,090
call three calls for each.

43
00:02:27,090 --> 00:02:29,800
And also the time complexity will be thrilled about it.

44
00:02:30,060 --> 00:02:32,820
So obviously, this is not the correct time complexity.

45
00:02:33,060 --> 00:02:37,440
So we can assume on an average our function will call on to other function calls.

46
00:02:37,440 --> 00:02:40,590
So we can say on an average the time complexity to the power.

47
00:02:40,590 --> 00:02:45,030
And basically it is it is definite that the time complexity is exponential.

48
00:02:45,840 --> 00:02:49,220
So this is very sure there are time complexities, exponential.

49
00:02:49,800 --> 00:02:51,180
So that is very short.

50
00:02:52,200 --> 00:02:54,080
Now, this is very, very bad.

51
00:02:54,180 --> 00:02:54,960
Exponential time.

52
00:02:54,960 --> 00:02:56,550
Complexity is very, very bad.

53
00:02:57,570 --> 00:03:00,870
Not if you will try to understand how many unique calls are there.

54
00:03:02,270 --> 00:03:03,860
How many unique calls are there?

55
00:03:05,570 --> 00:03:12,830
So basically, I have to reach from 12 to one, so the unequals will be 10, then 11, then 10 basically

56
00:03:12,830 --> 00:03:19,490
in this fashion, so unique calls will be to alonely basically I want to reach from nine to one.

57
00:03:19,790 --> 00:03:27,620
So total number of unique calls is simply big off end and calls total number of unique calls especially

58
00:03:27,620 --> 00:03:31,070
and calls and and each function we are doing constant work.

59
00:03:31,390 --> 00:03:33,370
So if you will see in each function.

60
00:03:33,680 --> 00:03:35,900
So all this is constant work, OK?

61
00:03:38,060 --> 00:03:42,190
So all of this is constant work through the number of calls is the total amount of time complexity.

62
00:03:42,470 --> 00:03:46,580
So the unique calls are basically big often and the rest everything.

63
00:03:47,730 --> 00:03:55,800
Rest of everything is repetition, that stuff, all the calls are repetition and recalculation because

64
00:03:55,930 --> 00:03:56,700
this big often.

65
00:03:57,400 --> 00:04:02,290
So what we will do so obvious solution when you are calculating for what you will do, you will save

66
00:04:02,470 --> 00:04:03,790
your answer at this point.

67
00:04:03,910 --> 00:04:08,120
And then when you need to calculate for it again, you will likely return your answer from here.

68
00:04:08,800 --> 00:04:14,200
Similarly, when you need to find out support for, you can likely use this answer.

69
00:04:14,950 --> 00:04:18,130
OK, so again, what we will do, we will calculate.

70
00:04:19,920 --> 00:04:24,270
We will calculate only once, then we will save and we will return.

71
00:04:24,870 --> 00:04:27,330
OK, so let us write the memorisation code.

72
00:04:27,900 --> 00:04:30,330
So memorisation means top down DEPI.

73
00:04:32,110 --> 00:04:34,260
So what is our approach, what we will do?

74
00:04:37,130 --> 00:04:40,050
So for starting the answer, we need, Eddie.

75
00:04:40,370 --> 00:04:42,260
So what will do, we will construct Benetti.

76
00:04:45,610 --> 00:04:48,770
Plus one side, so the first and next will be zero and the last.

77
00:04:48,790 --> 00:04:52,960
And so this is the next and the last index will be and plus one.

78
00:04:53,380 --> 00:04:55,410
And again, we have to initialize this area.

79
00:04:55,690 --> 00:04:58,580
So I have to initialize this area with invalid answer.

80
00:04:58,600 --> 00:05:00,940
So let's initializing this area with minus one.

81
00:05:03,990 --> 00:05:07,420
So why minus one, because minus one is invalid answer.

82
00:05:08,460 --> 00:05:12,300
So you have to initialize this area with any invalid answer.

83
00:05:12,330 --> 00:05:14,540
So minus one is invalid answers.

84
00:05:14,550 --> 00:05:16,000
Why missionising it with minus one?

85
00:05:16,020 --> 00:05:18,600
You can also initialize it with minus two, minus three.

86
00:05:18,600 --> 00:05:22,180
Anything, for example, like initializing this area with minus one.

87
00:05:22,920 --> 00:05:24,900
Then let's say this is index A.

88
00:05:27,110 --> 00:05:32,000
And let's say the name of this is answer, so what does onset of I contains?

89
00:05:32,160 --> 00:05:40,940
What does the meaning of of I so answer of is basically the minimum steps required to reach.

90
00:05:42,070 --> 00:05:43,210
From one to a.

91
00:05:44,790 --> 00:05:48,840
OK, so this is the meaning of onset of a minimum steps required to reach from.

92
00:05:49,730 --> 00:05:50,180
I to.

93
00:05:50,720 --> 00:05:52,100
And what do we want?

94
00:05:52,130 --> 00:05:56,040
We want to find out the minimum steps required to reach from nine to one.

95
00:05:56,270 --> 00:05:59,440
So basically my answer will be answered often.

96
00:05:59,450 --> 00:06:01,560
So this will be my big answer.

97
00:06:01,610 --> 00:06:03,750
This will be my big answer.

98
00:06:04,190 --> 00:06:08,970
So this one, this value, this indexes and the size that is in place.

99
00:06:08,970 --> 00:06:11,590
And so this index is in and this will be my answer.

100
00:06:11,600 --> 00:06:12,740
I will return this answer.

101
00:06:13,730 --> 00:06:17,780
So this is minimum steps required to reach from end one.

102
00:06:18,690 --> 00:06:22,560
So now we are ready to write the code, so let us write the code.

103
00:06:29,120 --> 00:06:29,790
So end.

104
00:06:31,600 --> 00:06:34,220
The name of the function is Lizzi M. Steps.

105
00:06:35,950 --> 00:06:42,160
Do so again, it will take and as input now what we have to do, we have to construct an area first.

106
00:06:42,670 --> 00:06:43,660
So let us make an.

107
00:06:45,140 --> 00:06:49,920
So instead, you can call it on set or you can also call it DEPI, it's your choice.

108
00:06:49,940 --> 00:06:51,680
So let's say I'm calling a dancer.

109
00:06:54,180 --> 00:06:59,190
What about the size of that issue as discussed, the size of that is and plus one that would have to

110
00:06:59,190 --> 00:07:01,410
do so, we have to initialize this area.

111
00:07:04,680 --> 00:07:07,350
And we have to initialize the area with invalid answer.

112
00:07:08,440 --> 00:07:15,560
So any invalid, valuable work, so you can write it like minus two, basically any invalid value.

113
00:07:15,580 --> 00:07:20,010
So let's say I am writing minus one because minus one is invalid answer.

114
00:07:20,620 --> 00:07:22,720
And what will do?

115
00:07:22,750 --> 00:07:24,280
We will return the helper function.

116
00:07:24,970 --> 00:07:26,350
We will write a helper function.

117
00:07:26,360 --> 00:07:27,690
We will call that helper function.

118
00:07:27,700 --> 00:07:30,670
We will pass and and we will pass Ansary.

119
00:07:32,310 --> 00:07:34,680
So now let us write the code for helper function.

120
00:07:38,980 --> 00:07:42,370
So the return type of helper function is in Pejar.

121
00:07:45,890 --> 00:07:50,180
So what this helper function will take, it will take two things, NT and Eddie.

122
00:07:53,520 --> 00:07:55,260
Let's say the name of that is answer.

123
00:07:56,920 --> 00:08:01,660
Now we have to write the code here, so what we will do, we will copy paste the same code.

124
00:08:04,710 --> 00:08:07,440
So this is the old Goldrick government or this called.

125
00:08:11,420 --> 00:08:16,610
And save the school now, what changes we have to do, so, again, the best case will be we'll see

126
00:08:16,640 --> 00:08:19,480
if the value of any is less than close to one, you can return zero.

127
00:08:20,030 --> 00:08:24,710
But here you have to write one more case if the value is already calculated.

128
00:08:25,130 --> 00:08:27,280
So basically, if I.

129
00:08:27,410 --> 00:08:28,040
Seraphin.

130
00:08:29,010 --> 00:08:35,520
It is not equal to minus one, so reinitialize that if it minus one, so if the of mind is not close

131
00:08:35,520 --> 00:08:38,789
to minus one, that means we have already calculated our answer.

132
00:08:39,179 --> 00:08:40,610
OK, so here what I'm doing.

133
00:08:42,059 --> 00:08:46,920
So here I am checking Jacov output exist.

134
00:08:48,970 --> 00:08:50,770
So let us check if output.

135
00:08:53,120 --> 00:08:57,470
Already exist, so if output already exist, then you can it return the output.

136
00:08:58,880 --> 00:09:03,830
So if I said if I start to question my nisson, you can like Leader Dunn answer because we have already

137
00:09:03,830 --> 00:09:04,930
concluded the answer.

138
00:09:06,040 --> 00:09:06,580
Simple.

139
00:09:07,760 --> 00:09:08,990
Otherwise, what we have to do.

140
00:09:09,980 --> 00:09:17,060
Same Golodryga solution X, Y and Z will be the maximum, then Kolon no header near the function is

141
00:09:17,060 --> 00:09:17,510
helper.

142
00:09:19,200 --> 00:09:21,490
And minus one, and we have to pass the answer ready?

143
00:09:21,960 --> 00:09:27,150
Again, the name of the function is Helper and by two they will pass the answer ready.

144
00:09:28,080 --> 00:09:31,410
So here the name of the function is Helper and Maitri.

145
00:09:32,500 --> 00:09:35,950
And possibly on Saturday, then we are calculating our answer.

146
00:09:36,010 --> 00:09:39,570
So this is my answer, but you cannot answer.

147
00:09:39,760 --> 00:09:41,470
You have to first save your answer.

148
00:09:42,520 --> 00:09:43,410
So what do you have to do?

149
00:09:46,390 --> 00:09:48,610
It will save you an answer for future use.

150
00:09:51,880 --> 00:09:57,670
OK, so one thing, the name of the name of the variable is also on set and here it is also on set.

151
00:09:57,700 --> 00:09:58,990
So let's change the name.

152
00:10:01,380 --> 00:10:02,580
So let's make it.

153
00:10:05,550 --> 00:10:06,210
Output.

154
00:10:09,400 --> 00:10:13,840
OK, so what do you do, you will return output, but first you will see your output.

155
00:10:15,790 --> 00:10:21,040
So first save, so I said often we are saving the answer for future use.

156
00:10:24,120 --> 00:10:29,340
And then you will return your output, so let's call this function M. Stepstool.

157
00:10:42,320 --> 00:10:43,820
And let's pass the value of an.

158
00:10:45,280 --> 00:10:46,840
So let's test our record.

159
00:10:46,870 --> 00:10:47,770
OK, so this one.

160
00:10:52,890 --> 00:10:54,390
Let's say the value of an is 11.

161
00:10:55,500 --> 00:11:01,590
So foreign for OK, so the first one is due to the recursive of and the second one is due to this memorisation

162
00:11:01,590 --> 00:11:01,890
called.

163
00:11:06,800 --> 00:11:11,390
So this approach is basically called top down DEPI.

164
00:11:12,910 --> 00:11:17,650
Why this is called top down, because first we are moving in this direction and then we are moving in

165
00:11:17,650 --> 00:11:19,310
this direction just like Fabianski.

166
00:11:20,140 --> 00:11:21,670
So this is called top down DP.

167
00:11:21,890 --> 00:11:25,210
And the name of this is basically memorisation.

168
00:11:26,350 --> 00:11:32,980
What is memorisation memorization is you simply write the recursive code and then you will your result

169
00:11:32,980 --> 00:11:33,370
also.

170
00:11:33,730 --> 00:11:41,400
So basically we copied our recursive code and then we are just storing, I said before returning.

171
00:11:41,620 --> 00:11:44,240
So we're just starting our answer before returning.

172
00:11:45,070 --> 00:11:48,360
So what about the time, complexity of the solution?

173
00:11:48,880 --> 00:11:50,800
So let's take a small example.

174
00:11:50,800 --> 00:11:52,340
Let's say the value of it is six.

175
00:11:52,360 --> 00:11:53,140
So what will happen?

176
00:11:53,590 --> 00:11:55,900
Six will call on five, five and then four.

177
00:11:55,900 --> 00:11:56,920
Four will call on three.

178
00:11:57,280 --> 00:12:00,530
Three will call on two and then two will call on one.

179
00:12:01,300 --> 00:12:02,200
So what will happen?

180
00:12:02,200 --> 00:12:03,150
When is the best case.

181
00:12:03,160 --> 00:12:05,020
So when will it and its answer then.

182
00:12:05,020 --> 00:12:06,110
Two by two.

183
00:12:06,130 --> 00:12:12,130
So I'll call on the right hand side when one is the best case, when will it answer then it will happen

184
00:12:12,130 --> 00:12:14,740
to its answer then three.

185
00:12:15,070 --> 00:12:16,480
So by three.

186
00:12:16,480 --> 00:12:17,630
So it will call on one.

187
00:12:17,950 --> 00:12:19,180
So when is the best case?

188
00:12:19,180 --> 00:12:20,290
It will likely be done.

189
00:12:20,320 --> 00:12:23,410
Its answer then three will return answer to four.

190
00:12:23,830 --> 00:12:25,580
So four is resolved by two.

191
00:12:25,600 --> 00:12:27,640
So there will be a call until now.

192
00:12:27,910 --> 00:12:34,000
At this point when we are returning the answer, we will also see the answer for two so we already know

193
00:12:34,000 --> 00:12:34,720
the answer for two.

194
00:12:34,720 --> 00:12:37,520
So very directly written, the answer simple.

195
00:12:37,900 --> 00:12:41,850
Similarly, when we are returning the answer for three, I will answer for three.

196
00:12:42,250 --> 00:12:44,020
Now I will answer for four.

197
00:12:44,110 --> 00:12:45,880
So I will store the answer for four.

198
00:12:46,980 --> 00:12:53,640
So, five, it is now reduced by two or three, then four, six, six is dugal by two, so it will call

199
00:12:53,850 --> 00:12:55,710
on three and six by three.

200
00:12:55,710 --> 00:12:58,970
So they will be Ashqelon, two for three.

201
00:12:59,310 --> 00:13:00,540
We already know the answer.

202
00:13:00,930 --> 00:13:06,210
We have stored the answer here, so we will directly return the answer now for two, we have already

203
00:13:06,210 --> 00:13:07,200
stored the answer here.

204
00:13:07,350 --> 00:13:11,630
We have already calculated and stored the answer, so we will likely return the answer.

205
00:13:12,480 --> 00:13:15,300
And finally, thirty five will also return the answer.

206
00:13:15,300 --> 00:13:19,710
Then six will call Continental and we will also slow down to four five.

207
00:13:19,710 --> 00:13:21,330
Then we will store the answer for six.

208
00:13:21,600 --> 00:13:25,770
So we are storing the answer for six and then we are returning our answer and then we will return the

209
00:13:25,770 --> 00:13:26,200
answer.

210
00:13:26,970 --> 00:13:29,160
So how many total number of unique calls?

211
00:13:30,810 --> 00:13:33,450
So total number of unique calls is basically this one.

212
00:13:38,120 --> 00:13:45,440
So they are basically unicorns, so the value of animal sex, that's why succinylcholine, so the complexity

213
00:13:45,440 --> 00:13:49,070
is basically big, often you will see in each function.

214
00:13:49,250 --> 00:13:53,310
So this is constant, this constant, constant work, constant work, constant work.

215
00:13:53,540 --> 00:13:54,890
So each function.

216
00:13:57,580 --> 00:14:04,720
Is doing constant work and total number of functions called total function is called.

217
00:14:05,910 --> 00:14:11,310
It's basically big off, and so what is the time, complexity, so total function called multiply burdened

218
00:14:11,310 --> 00:14:12,090
by each function.

219
00:14:12,120 --> 00:14:13,920
So that's why the time complexity is big.

220
00:14:13,920 --> 00:14:20,400
Often see by using memorisation our time complexity becomes linear.

221
00:14:20,760 --> 00:14:26,850
Earlier due to recursion, when we was when we were using alligations or time, complexity was exponential

222
00:14:27,270 --> 00:14:27,990
due to the power.

223
00:14:27,990 --> 00:14:31,420
And we can assume that on an average there are two goals.

224
00:14:32,130 --> 00:14:33,250
So that's very true to the power.

225
00:14:33,280 --> 00:14:37,320
And so from exponential, we are able to reach linear time complexity.

226
00:14:37,590 --> 00:14:40,910
So that is the power of top down beyond memorization.

227
00:14:42,300 --> 00:14:44,930
So I will see you in the next one by.