1
00:00:01,790 --> 00:00:02,490
Hi, everyone.

2
00:00:02,510 --> 00:00:08,780
So in this video, we are going to understand this topic, DEPI, Danek programming, so many people

3
00:00:08,780 --> 00:00:14,190
used to scared of danek programming, dippie, but what we will do, we will only be in the right way.

4
00:00:14,820 --> 00:00:20,210
We will start from a very easy problem and we will slowly build up concept and then we will solve a

5
00:00:20,210 --> 00:00:21,150
much harder problem.

6
00:00:21,650 --> 00:00:25,090
So let's start with deep trouble understanding the deep.

7
00:00:25,100 --> 00:00:26,850
Let us consider a very small example.

8
00:00:27,440 --> 00:00:29,840
So let us consider the Fibonacci series.

9
00:00:30,200 --> 00:00:36,080
So what is happening is it is so difficult, I can say is first to damselfish zero and one, and we're

10
00:00:36,080 --> 00:00:41,690
finding out the next time you will at previous to so it will be one then you will like previous to find

11
00:00:41,690 --> 00:00:43,000
out the current term.

12
00:00:43,010 --> 00:00:44,840
And similarly this will go on.

13
00:00:44,870 --> 00:00:49,400
So this will be three, then five, then eight, then 13 and so on.

14
00:00:50,300 --> 00:00:56,840
So for finding out the current term, you will add previous to so this is zero Fibonacci number.

15
00:00:56,870 --> 00:00:59,420
This is first Fibonacci number and so on.

16
00:00:59,950 --> 00:01:05,660
So if you remember, we have already solved the question of finding the net Fibonacci number for finding

17
00:01:05,660 --> 00:01:06,950
out the net number.

18
00:01:07,280 --> 00:01:08,010
So let's see the.

19
00:01:09,270 --> 00:01:10,690
So this is very simple code.

20
00:01:11,090 --> 00:01:17,970
Now, let us try to understand this code so this Fibonacci function will find out the network number.

21
00:01:17,990 --> 00:01:19,040
So this is the best case.

22
00:01:19,040 --> 00:01:25,040
If the value of any zero, I will return zero zero zero and the first number is one.

23
00:01:25,190 --> 00:01:26,750
So that's why I'm returning one.

24
00:01:27,260 --> 00:01:32,990
Then for finding out the current Fibonacci number, it will be the addition of and minus one previous

25
00:01:32,990 --> 00:01:35,350
one and minus two previous of previous.

26
00:01:35,720 --> 00:01:42,470
So we are finding out and number what we will do, we will add previous to Fibonacci number so often

27
00:01:42,470 --> 00:01:44,420
minus one end above and minus two.

28
00:01:45,700 --> 00:01:51,130
Simple, but the problem with this code is basically this code is very, very slow.

29
00:01:52,710 --> 00:01:54,490
This court is very, very slow.

30
00:01:54,810 --> 00:01:56,040
So why this cold, this low?

31
00:01:56,310 --> 00:02:00,490
Because if we'll see the time complexity, so let us analyze the time complexity.

32
00:02:01,080 --> 00:02:02,700
So what is happening here and.

33
00:02:04,930 --> 00:02:10,419
So I have and now let's go inside the function, so inside the function here, I'm doing constant work,

34
00:02:11,140 --> 00:02:17,830
then this and function and function, it is calling on to their function and then it is adding those

35
00:02:17,830 --> 00:02:18,430
two values.

36
00:02:18,670 --> 00:02:21,130
So basically, this function is doing constant work.

37
00:02:21,820 --> 00:02:23,290
This function is doing constant work.

38
00:02:23,300 --> 00:02:26,240
It is just calling one and minus one and minus two.

39
00:02:26,770 --> 00:02:34,180
So basically this is a function of function is calling on and minus one and it is calling on and minus

40
00:02:34,180 --> 00:02:34,360
two.

41
00:02:35,110 --> 00:02:35,670
Simple.

42
00:02:36,010 --> 00:02:42,940
So similarly this and minus one will call on and minus two and minus three similarly and minus two will

43
00:02:42,940 --> 00:02:46,690
call on and minus three and and minus four.

44
00:02:49,130 --> 00:02:50,360
And this will go on.

45
00:02:51,440 --> 00:02:56,390
OK, so this will go on now at this level, how many functions are there?

46
00:02:56,390 --> 00:03:01,040
So when at this level, how many functions are there to add this level?

47
00:03:01,040 --> 00:03:02,780
How many functions are there for?

48
00:03:03,020 --> 00:03:06,010
Similarly, at the next level, I will have eight functions call.

49
00:03:06,560 --> 00:03:11,840
And similarly, at the last level, they can be potentially due to the power and functions call.

50
00:03:12,650 --> 00:03:13,730
So exactly.

51
00:03:13,880 --> 00:03:15,710
They will not be told about any functions.

52
00:03:15,710 --> 00:03:16,790
Call why?

53
00:03:16,970 --> 00:03:18,100
Because of considerately.

54
00:03:18,110 --> 00:03:18,890
So what will happen.

55
00:03:18,890 --> 00:03:24,200
Three will call on two and one, then two will call on one and zero.

56
00:03:24,980 --> 00:03:27,110
So one will return, zero will return.

57
00:03:27,110 --> 00:03:29,010
And similarly when will return from here.

58
00:03:29,540 --> 00:03:32,260
So what will happen to Destry if we'll see that carefully?

59
00:03:32,930 --> 00:03:37,880
This is basically left biased where this is left biased because in the left hand side this is decreasing

60
00:03:37,880 --> 00:03:42,530
by one and minus one then and minus two, then three to one.

61
00:03:42,560 --> 00:03:46,850
So in the left hand side it is decreasing by one, but in the right hand side it is decreasing by two.

62
00:03:47,240 --> 00:03:49,910
So and minus two then and minus four and so on.

63
00:03:50,150 --> 00:03:52,240
Basically this tree is left biased.

64
00:03:52,280 --> 00:03:56,580
So in the left hand side it will be much bigger and the right hand side it will be smaller.

65
00:03:57,450 --> 00:04:00,620
Okay, so this fluidity, this, this will be the recursion.

66
00:04:00,800 --> 00:04:02,060
So this is left biased.

67
00:04:02,750 --> 00:04:09,560
But even if this is left biased, if you will add all these functions, call if you will add these functions,

68
00:04:09,560 --> 00:04:11,180
call and you will do the calculation.

69
00:04:11,570 --> 00:04:17,959
So total number of functions will be two to the power and so two to the right are the total number of

70
00:04:17,959 --> 00:04:18,570
functions called.

71
00:04:18,860 --> 00:04:23,420
And each function, each function is doing basically constant work.

72
00:04:23,690 --> 00:04:27,220
It is just checking the base case and then it is using plus operator.

73
00:04:27,560 --> 00:04:29,210
OK, so each function is doing.

74
00:04:30,370 --> 00:04:34,040
Constant work, and these are the total number of functions gone.

75
00:04:34,300 --> 00:04:38,770
So basically the time, complexity of our solution is due to the power and.

76
00:04:39,860 --> 00:04:40,790
So for this cold.

77
00:04:41,880 --> 00:04:47,640
Why this is slow, this is slow because the time complexities to do the power, and so this is very,

78
00:04:47,640 --> 00:04:49,390
very bad, very, very bad.

79
00:04:49,920 --> 00:04:51,770
So definitely we want something better.

80
00:04:53,150 --> 00:04:54,970
So even if you want to find out.

81
00:04:55,040 --> 00:04:56,300
So let me show you.

82
00:04:58,040 --> 00:05:02,060
So even if you will try to find out 53 first.

83
00:05:04,390 --> 00:05:10,030
Let us try to find out 23 number, so it is giving me output in one second.

84
00:05:11,340 --> 00:05:20,510
Now, let us try to find out the 58 Fibonacci number so 50 and see it post so what it will do.

85
00:05:20,520 --> 00:05:22,050
So it is doing the calculation.

86
00:05:22,320 --> 00:05:24,210
It will take a lot of a lot of time.

87
00:05:24,240 --> 00:05:25,680
So I am closing my output.

88
00:05:25,680 --> 00:05:29,340
I am closing this screen because it's going to take a lot of lot of time.

89
00:05:30,560 --> 00:05:36,680
So now you can understand our previous solution is to to the power in debt, so I'm not able to find

90
00:05:36,680 --> 00:05:39,790
out the 58 number, if you will, run the code.

91
00:05:39,800 --> 00:05:41,880
It is going to take a lot of a lot of time.

92
00:05:42,590 --> 00:05:44,400
Now, how can we solve this problem?

93
00:05:44,960 --> 00:05:46,110
So what is happening here?

94
00:05:46,130 --> 00:05:52,600
Let me throw that gently and then we will try to understand what is the problem by the time complexities

95
00:05:52,620 --> 00:05:53,390
to the power in.

96
00:05:54,560 --> 00:05:56,440
OK, so let's see.

97
00:05:56,900 --> 00:05:59,990
So you have known and will call on and minus one.

98
00:06:00,860 --> 00:06:01,730
And minus two.

99
00:06:02,950 --> 00:06:07,480
Then minister will call on previous to so it will call on and minus two and then minus three.

100
00:06:09,190 --> 00:06:15,260
Then similarly, it will go on and ministry and similarly on the left hand side, so it will go on.

101
00:06:16,250 --> 00:06:21,790
Now, what will happen when you will find out the answer of any ministry so it will return done when

102
00:06:21,790 --> 00:06:25,060
ministers and ministers will answer to and minus one.

103
00:06:25,630 --> 00:06:26,680
Now, what is happening here?

104
00:06:26,960 --> 00:06:32,440
When and minister will get the answer from the left hand side, it will call on right inside and what

105
00:06:32,440 --> 00:06:36,130
is right inside and ministry and if it will, Ticketfly.

106
00:06:36,430 --> 00:06:40,780
We have already calculated and ministry, but here we are calculating again.

107
00:06:41,930 --> 00:06:48,320
We will again calculate and ministry, we will do the same calculation again, so any ministry will

108
00:06:48,320 --> 00:06:52,850
call on and minus two and minus four and and minus five.

109
00:06:53,120 --> 00:06:55,970
So basically here we solve this problem.

110
00:06:56,810 --> 00:06:58,600
We find out down to foreign ministry.

111
00:06:58,610 --> 00:07:03,050
But here again, when we reach here, women, men and women will call on right.

112
00:07:03,050 --> 00:07:05,390
And say we will again do the same calculation.

113
00:07:05,840 --> 00:07:07,430
We will do the same work.

114
00:07:07,850 --> 00:07:11,380
So basically, we are repeating our work similarly.

115
00:07:11,780 --> 00:07:17,420
So when and minus and we are done the answer to then and we'll call on and minister and here if will

116
00:07:17,420 --> 00:07:18,170
see carefully.

117
00:07:18,200 --> 00:07:19,940
We have already sold our answer.

118
00:07:19,940 --> 00:07:22,090
We have already done that calculation, Foreign Minister.

119
00:07:22,100 --> 00:07:24,530
But here we are again doing the calculation.

120
00:07:24,540 --> 00:07:25,320
Foreign Minister.

121
00:07:25,820 --> 00:07:31,520
So the main problem by that time completely to the power end is basically we are repeating our work.

122
00:07:33,410 --> 00:07:34,660
We are repeating ourselves.

123
00:07:35,820 --> 00:07:39,270
We have Alladin and ministry, then vital and ministry again.

124
00:07:39,900 --> 00:07:42,790
So what is the simple solution to avoid this problem?

125
00:07:42,810 --> 00:07:44,060
So the obvious solution.

126
00:07:44,070 --> 00:07:49,590
So this is very obvious solution and obvious solution is when you have done the work, basically store

127
00:07:49,590 --> 00:07:52,620
it somewhere and then use it in the future.

128
00:07:52,830 --> 00:07:54,990
So to store and use in future.

129
00:07:56,800 --> 00:07:58,780
OK, so this is a very simple solution.

130
00:07:58,810 --> 00:08:05,160
This is very obvious also, if you have done the calculation foreign ministry, then store the answer

131
00:08:05,230 --> 00:08:06,100
foreign ministry.

132
00:08:06,100 --> 00:08:09,730
So store it somewhere to store it somewhere, basically.

133
00:08:10,090 --> 00:08:14,950
And then we are doing then we again, when you are doing the calculation, foreign ministry, so doing

134
00:08:15,280 --> 00:08:21,550
instead of doing the calculation, you can take the answer from the store, the variable simple.

135
00:08:22,330 --> 00:08:24,470
So basically store and use in future.

136
00:08:24,490 --> 00:08:25,990
So this is a very simple solution.

137
00:08:26,650 --> 00:08:30,330
So if you will store, if you will store.

138
00:08:30,940 --> 00:08:33,640
So how many number of unique calls will be there?

139
00:08:35,710 --> 00:08:40,309
So I'm talking about unique, a number of functions called so unique, a number of functions called

140
00:08:40,330 --> 00:08:46,510
will be and only why because and we'll call and minutes and then I will call in and minus two.

141
00:08:46,510 --> 00:08:52,150
And similarly Telvin and we will store the list all down to four one install down to four to restore

142
00:08:52,150 --> 00:08:53,170
order and support and minus.

143
00:08:53,170 --> 00:08:57,580
And we restore the answerphone and so basically total number of functions call will be in.

144
00:08:59,060 --> 00:09:04,700
OK, addressed all calls will be repetition only, and since addressed all calls are repetition, we

145
00:09:04,700 --> 00:09:08,090
can likely take the answer from the stored variables, from the stored answer.

146
00:09:08,810 --> 00:09:13,730
Obviously, I know we can solve this question creatively also, but I want to improve our recursive

147
00:09:13,730 --> 00:09:14,270
solution.

148
00:09:14,660 --> 00:09:17,130
OK, so how can we improve our recursive solution?

149
00:09:17,480 --> 00:09:19,970
So what we will do, we will make an error.

150
00:09:21,350 --> 00:09:25,700
So I'm going to construct an array of size and plus one.

151
00:09:26,900 --> 00:09:32,370
So that means my first index will be zero and my last index will be in simple.

152
00:09:33,440 --> 00:09:39,590
Now what I will do, I will initialize this area with zeroes, so I will initialize this area with zeros

153
00:09:39,830 --> 00:09:41,600
in this area is filled with zeros.

154
00:09:42,260 --> 00:09:43,630
So what is my logic?

155
00:09:43,640 --> 00:09:44,780
Logic is very simple.

156
00:09:45,320 --> 00:09:47,450
We will store and you reduce the value.

157
00:09:48,510 --> 00:09:56,010
As discussed above, I'm going to store and reuse our values, so what we will do so as soon is, for

158
00:09:56,010 --> 00:10:00,930
example, as soon as you are able to find out what is a fifth one, I can remember what I will do.

159
00:10:01,200 --> 00:10:02,760
I will go to the fifth value.

160
00:10:03,030 --> 00:10:05,810
I will go to the fifth index and I will store the value.

161
00:10:06,240 --> 00:10:07,890
So whenever in the future.

162
00:10:08,640 --> 00:10:14,640
Whenever in the future you want to find out Fabianski of five, then you will go to the fifth index,

163
00:10:14,820 --> 00:10:18,280
you will check is zero percent or there is some value.

164
00:10:18,480 --> 00:10:24,690
So if there is some value present, that means I have already sold this question so I can directly use

165
00:10:24,690 --> 00:10:25,170
this value.

166
00:10:26,070 --> 00:10:30,300
Similarly, if in future you want to find Funaki of three.

167
00:10:30,480 --> 00:10:36,650
So what you will do, you will go to index three and you will check oh zero percent there.

168
00:10:36,730 --> 00:10:38,730
That means I have not done the calculation.

169
00:10:38,970 --> 00:10:41,220
So let's do the calculation for above three.

170
00:10:41,880 --> 00:10:45,380
And after doing the calculation, let's put the value at the third index.

171
00:10:45,750 --> 00:10:51,120
So whenever in future you want to calculate Fabo three again, what you will do, you will go to index

172
00:10:51,120 --> 00:10:52,710
three and you will check.

173
00:10:53,040 --> 00:10:55,920
So is there any value present that is different from zero?

174
00:10:56,190 --> 00:11:00,810
If there is a value which is different from zero, that means I have already sold Fabianski of three.

175
00:11:01,110 --> 00:11:03,720
So that means I can take the value from here.

176
00:11:04,560 --> 00:11:08,340
OK, so basically that is how we will be able to implement the solution.

177
00:11:08,730 --> 00:11:11,910
We can store the values and then we will reuse our values.

178
00:11:13,310 --> 00:11:15,140
So now let's write the code.

179
00:11:18,850 --> 00:11:25,810
So let's create a function that will be integer, and the name of the function is when I get to see

180
00:11:25,930 --> 00:11:27,310
what this when will take.

181
00:11:28,320 --> 00:11:35,010
I have to find out and that number, and it will take area's input, so this area, the area that we

182
00:11:35,010 --> 00:11:41,940
will initialized with all zeroes, again, the base case will be same if the value of any is zero or

183
00:11:41,940 --> 00:11:43,410
the value of this one.

184
00:11:45,570 --> 00:11:48,330
I will return when the biscuit is no difference.

185
00:11:49,410 --> 00:11:52,170
Now, there will be one more condition, so if.

186
00:11:55,110 --> 00:12:03,480
He often very often is not close to zero, that means you have already solved this problem for a network.

187
00:12:03,740 --> 00:12:04,070
No.

188
00:12:04,290 --> 00:12:09,300
So that means you can directly return without doing anything so you can return every often.

189
00:12:10,230 --> 00:12:14,600
It is I really realized that if it grows and if the current value is not zero.

190
00:12:14,880 --> 00:12:19,380
So that means I have already solved this problem and I have stored the answer.

191
00:12:20,280 --> 00:12:24,450
So if this is not the case, that means we are doing the calculation for the first time.

192
00:12:25,080 --> 00:12:26,700
So what will be my output?

193
00:12:29,270 --> 00:12:35,060
What I have to do over finding out and not knocking them, but I have to call on and minus one and minus

194
00:12:35,060 --> 00:12:35,300
two.

195
00:12:38,960 --> 00:12:41,510
So I'm calling one and minus one and minus two.

196
00:12:43,300 --> 00:12:50,390
Simple now, once you have calculated your output, what you have to do first, you restore your output.

197
00:12:50,950 --> 00:12:58,270
So let us store my output first and then we will return the output and then we will return our output.

198
00:12:59,430 --> 00:13:07,890
OK, so first story then did an output, so I'm storing the value for future use, so store.

199
00:13:09,280 --> 00:13:10,210
For future use.

200
00:13:13,210 --> 00:13:19,930
Simple, now let us discuss their time, complexity for this matter of two so you will see carefully.

201
00:13:21,480 --> 00:13:25,020
But over time, complexity, so you have an.

202
00:13:28,120 --> 00:13:32,680
So you have seen what will happen, so and will call on and minus one.

203
00:13:34,360 --> 00:13:36,580
Then minus one and minus two.

204
00:13:38,410 --> 00:13:46,120
Then in two will call one end ministry and this will go on finally to then one and then zero.

205
00:13:47,940 --> 00:13:48,980
And then what will happen?

206
00:13:48,990 --> 00:13:56,910
So when will it sunset at sunset and similarly to it and the answer similarly and ministry will return

207
00:13:56,910 --> 00:13:57,560
its answer.

208
00:13:58,250 --> 00:14:06,120
OK, so now when you reach and minus two, what will happen and minus two will call on and minus four

209
00:14:07,410 --> 00:14:12,010
and and minus four is already calculated and minus four.

210
00:14:12,030 --> 00:14:12,780
We have already started.

211
00:14:12,780 --> 00:14:15,850
If you see I have an A minus four here so.

212
00:14:15,870 --> 00:14:16,710
And a minus what.

213
00:14:16,710 --> 00:14:19,560
We have already calculated the value and we are able to restore the value.

214
00:14:20,590 --> 00:14:25,900
So this will be you will call here and my network will directly return the answer, because we have

215
00:14:25,900 --> 00:14:29,860
stored the values for nd minus for then and minus two will return.

216
00:14:29,880 --> 00:14:33,360
The answer to one, minus one and minus one will call on right inside.

217
00:14:33,790 --> 00:14:35,110
This will be and minus three.

218
00:14:36,190 --> 00:14:41,860
And directly and ministry, we will return the answer, so we have already stored the value, we have

219
00:14:41,860 --> 00:14:44,040
already done the calculation and we have stored the value.

220
00:14:44,200 --> 00:14:48,670
So so minus ministry will directly return the value it will not call on and minus four and then minus

221
00:14:48,670 --> 00:14:50,520
five, it will directly return the value.

222
00:14:51,460 --> 00:14:59,800
So minus on the value to N now N will call on and minus twenty eight inside and, and minus two will

223
00:14:59,800 --> 00:15:05,740
directly return the answer because we have already calculated the value and we will restore the value

224
00:15:06,340 --> 00:15:07,990
so it will directly return the value.

225
00:15:08,650 --> 00:15:10,470
So how many functions are there.

226
00:15:10,780 --> 00:15:12,100
So we will see carefully.

227
00:15:13,610 --> 00:15:19,430
So there are total end calls in the left hand side and is calling on in Minnesota that in my history

228
00:15:19,430 --> 00:15:26,190
and my history and anyone so there and concentrate left inside and each function is calling on the right

229
00:15:26,190 --> 00:15:31,520
hand side once everyone will call them right inside once and they will likely return the answer.

230
00:15:32,000 --> 00:15:37,080
So in total, there will be N and each function will go on right hand side so and listen.

231
00:15:37,400 --> 00:15:38,480
So there will be total.

232
00:15:38,690 --> 00:15:42,220
So these are the total number of calls and if you will see the function.

233
00:15:42,830 --> 00:15:44,280
So we are doing constant work.

234
00:15:44,750 --> 00:15:46,890
So this is we are doing checking.

235
00:15:47,060 --> 00:15:48,680
Then again, we are doing some checks.

236
00:15:49,100 --> 00:15:50,720
Then we are finding out the output.

237
00:15:50,960 --> 00:15:52,100
So this is constant work.

238
00:15:52,130 --> 00:15:56,390
We are just using blitz operator agame, constant work and then we are returning our output.

239
00:15:57,400 --> 00:16:03,700
So basically, each function is doing constant work, each function is doing constant work, and there

240
00:16:03,700 --> 00:16:05,340
are basically two to three hour angles.

241
00:16:05,590 --> 00:16:08,530
So that time complexity will be bigger off and.

242
00:16:09,670 --> 00:16:16,030
This is the time complexity, so let's see first, our time complexity was due to the power end, but

243
00:16:16,030 --> 00:16:23,490
now our time complexities big off and see how much we are improving and we are improving a lot.

244
00:16:24,830 --> 00:16:31,910
So if we see this cushion, if you will see this in the perspective of Eddie, so let's take an example,

245
00:16:31,910 --> 00:16:34,590
let's say the value of and is it.

246
00:16:35,030 --> 00:16:35,870
So what is happening?

247
00:16:35,900 --> 00:16:39,360
We are constructing an area of nine size and plus one size.

248
00:16:39,980 --> 00:16:43,430
So the first index is zero and the last index is eight.

249
00:16:43,910 --> 00:16:44,750
So what will happen?

250
00:16:45,140 --> 00:16:48,890
Eight will call on seven to find out the answer.

251
00:16:49,050 --> 00:16:50,450
Seven will call on six.

252
00:16:50,450 --> 00:16:51,740
Six will call on five.

253
00:16:52,100 --> 00:16:53,840
And similarly, this call will go on.

254
00:16:53,870 --> 00:16:57,290
So this is, let's say two, then I have one.

255
00:16:57,500 --> 00:17:00,500
So two will call on one and two will call on zero.

256
00:17:00,800 --> 00:17:02,660
And they both will return the answer.

257
00:17:02,990 --> 00:17:04,430
So finally, two will be filled.

258
00:17:05,180 --> 00:17:07,190
So after filling out the two, what will happen?

259
00:17:07,730 --> 00:17:12,800
Three will be filled, then four will be filled, then five, then six, then seven and then eight.

260
00:17:12,980 --> 00:17:14,569
And then I will return.

261
00:17:15,890 --> 00:17:17,089
I will return this value.

262
00:17:17,550 --> 00:17:20,099
OK, so how this ad is getting filled.

263
00:17:20,300 --> 00:17:25,460
So first I'm going in this direction, new direction, and then I am feeling this very.

264
00:17:26,740 --> 00:17:32,740
This way, so basically we are traversing the area two times, first we are going in the left hand side

265
00:17:33,040 --> 00:17:36,610
and then we are when we are going in the right hand side, we are filling the area.

266
00:17:37,090 --> 00:17:38,160
We are filling this area.

267
00:17:38,530 --> 00:17:41,790
So this area was initialized with Xeros initially.

268
00:17:41,800 --> 00:17:43,840
This area was in initialized with zeroes.

269
00:17:43,990 --> 00:17:49,700
So first when the left hand side and then we will go from left to right inside this area will get filled.

270
00:17:50,530 --> 00:17:55,870
Now if we will see carefully, if you will observe carefully one obvious improvement, what we can do.

271
00:17:56,050 --> 00:18:02,050
So instead of going first in the left hand side, then the right hand side, we can directly go right

272
00:18:02,050 --> 00:18:04,090
hand side, OK, we can directly.

273
00:18:04,360 --> 00:18:07,390
So what we can do, we can directly, we can fill this area.

274
00:18:08,290 --> 00:18:08,970
What we will do.

275
00:18:09,190 --> 00:18:14,590
You take an area, you know that at a and these two values are fixed.

276
00:18:15,400 --> 00:18:20,770
So I can instead of going instead of using this approach first go left and then go right, what can

277
00:18:20,770 --> 00:18:21,060
I do?

278
00:18:21,190 --> 00:18:23,200
I can actually fill this area in this way.

279
00:18:23,530 --> 00:18:25,480
I can iteratively fill this area.

280
00:18:27,240 --> 00:18:32,970
OK, I can I totally disagree, because if you had previous to you will get to her, then you will at

281
00:18:32,970 --> 00:18:37,410
previous two, so you will get three here, you will add the previous two, you will get five here and

282
00:18:37,410 --> 00:18:37,770
so on.

283
00:18:38,550 --> 00:18:40,960
So we can actually we can agree to disagree.

284
00:18:40,980 --> 00:18:42,570
So let's write the code for this one.

285
00:18:48,030 --> 00:18:50,130
So I will be in for about three.

286
00:18:51,250 --> 00:18:56,880
OK, so what it will do, it will take the well often it will not take in input, OK, because it will

287
00:18:56,880 --> 00:18:58,560
construct better inside the function.

288
00:18:59,260 --> 00:19:01,000
We will construct better inside the function.

289
00:19:01,440 --> 00:19:10,560
So let us create dynamic at because the value of this variable so new it and we are creating variable

290
00:19:10,560 --> 00:19:11,090
sized area.

291
00:19:11,100 --> 00:19:13,560
So you should create variable size daily.

292
00:19:14,910 --> 00:19:20,910
Using dynamic education, I want to create size and plus one and plus one.

293
00:19:22,020 --> 00:19:25,130
Now, the first two values are fixed 32.

294
00:19:25,770 --> 00:19:26,600
I have zero.

295
00:19:27,240 --> 00:19:29,030
First of talking numbers are fixed.

296
00:19:29,040 --> 00:19:30,450
So at one, I have one.

297
00:19:31,440 --> 00:19:35,970
Now I'd have to do I will fill this area from left to right addictively.

298
00:19:36,300 --> 00:19:41,960
So I have to start feeling from index to I will go till index in and I placeless.

299
00:19:42,660 --> 00:19:43,530
So what I have to do.

300
00:19:44,780 --> 00:19:48,950
So if you want to find out I why this is edition of I mean, this one.

301
00:19:51,110 --> 00:19:52,250
And I a minus to.

302
00:19:55,370 --> 00:20:01,850
Simple and finally, what we can do, finally, we can return our output and our output is a matter

303
00:20:01,880 --> 00:20:05,270
of and by doing this is wrong, why this is wrong?

304
00:20:05,270 --> 00:20:08,220
Because you have created the error dynamically.

305
00:20:08,240 --> 00:20:10,280
So before it ends in the area, what will do?

306
00:20:10,550 --> 00:20:11,650
We will delete our area.

307
00:20:11,780 --> 00:20:13,310
OK, we have to delete ourself.

308
00:20:13,520 --> 00:20:14,750
We have allocated the memory.

309
00:20:14,750 --> 00:20:16,890
Now we have to delete the memory ourself.

310
00:20:17,240 --> 00:20:18,440
So let's free the memory.

311
00:20:19,410 --> 00:20:20,100
So delete.

312
00:20:22,730 --> 00:20:28,650
Dilatory, so I have to leave the area, but if you leave the area, how can you return the value?

313
00:20:28,940 --> 00:20:31,000
So that means I have to store value first.

314
00:20:32,510 --> 00:20:34,070
So let's first store the value.

315
00:20:35,550 --> 00:20:36,750
So I'm starting Disvalue.

316
00:20:39,440 --> 00:20:44,900
So after destroying the value in output variable, delete data and then return the output.

317
00:20:49,000 --> 00:20:52,780
So this is the cold, so let's call on February.

318
00:20:57,080 --> 00:21:01,400
So I'm calling the function and I will give and as input.

319
00:21:02,930 --> 00:21:07,550
So now I'm calling both the functions, I'm calling for three function, so this one.

320
00:21:08,590 --> 00:21:10,450
And then I'm calling other oil function.

321
00:21:11,300 --> 00:21:12,190
OK, so let's see.

322
00:21:16,320 --> 00:21:18,000
OK, so this is actually free of to.

323
00:21:25,790 --> 00:21:27,350
The value of this 35.

324
00:21:33,720 --> 00:21:40,390
So the value of N is basically 40 Norzai, so 50 gives the output instantaneously.

325
00:21:40,590 --> 00:21:42,190
So this function is taking time.

326
00:21:42,930 --> 00:21:44,250
Let's give a bigger value.

327
00:21:46,120 --> 00:21:49,150
So let's give the value of N four to five C.

328
00:21:50,420 --> 00:21:55,870
This addictively approach, it is giving me answer in just one second, whereas the second one, due

329
00:21:55,880 --> 00:21:58,710
to the power and function, it is taking a lot of time.

330
00:21:58,730 --> 00:21:59,030
OK.

331
00:22:00,160 --> 00:22:05,570
So dysfunction is returning value instantaneously and dysfunction is taking time.

332
00:22:06,040 --> 00:22:08,740
So let us also call this function of two.

333
00:22:10,420 --> 00:22:15,690
So for calling the function of two, basically you have to construct Benetti, so let us create an eddy.

334
00:22:23,890 --> 00:22:28,300
So I have to create an area of plus one size and I have to initialize this area with Zardoz.

335
00:22:39,850 --> 00:22:42,880
And then let's call all the functions, so.

336
00:22:47,590 --> 00:22:52,330
Let's call the function of two and and you have to pass, Eddie, also.

337
00:22:54,930 --> 00:22:58,720
OK, so I'm calling for both three function to function and function.

338
00:22:59,730 --> 00:23:01,860
So let's see, let's compare all this.

339
00:23:03,660 --> 00:23:08,360
So let's give the value of N four to five so C these two are giving me.

340
00:23:08,370 --> 00:23:10,990
So this is for both to end the system of two, OK.

341
00:23:11,010 --> 00:23:13,440
So basically the answer is coming out to be different.

342
00:23:13,440 --> 00:23:14,100
Very different.

343
00:23:15,250 --> 00:23:20,500
So this is OK, OK over here instead of one that should be written, so let me correct it.

344
00:23:22,100 --> 00:23:25,030
So instead of mind, this should be an OK society.

345
00:23:25,880 --> 00:23:30,830
Well, guess what, one mistake, he had a train platform, so there should be it should be in.

346
00:23:31,550 --> 00:23:33,700
So now let's run our program again.

347
00:23:37,520 --> 00:23:43,280
So if I give the value of N four to five, so this is basically four of three and this is above two

348
00:23:43,490 --> 00:23:45,540
and one will take a lot of time.

349
00:23:45,560 --> 00:23:47,120
So let's not wait for.

350
00:23:48,840 --> 00:23:49,530
When function.

351
00:23:51,100 --> 00:23:56,500
So this is for one function, it is taking a lot of time, so if you will see it carefully.

352
00:23:58,230 --> 00:24:03,750
The first method due to recursion, it takes two to the power, and so these are the total number of

353
00:24:03,750 --> 00:24:04,140
calls.

354
00:24:05,420 --> 00:24:12,210
In the second matter, the total number of calls was to win, so the time complexity was big often why

355
00:24:12,260 --> 00:24:17,180
it is to win, because first we will go in the left hand side, then we will go in the right hand side

356
00:24:17,180 --> 00:24:23,870
and the size of the arrays and so unpleasant to calls in the third approach, the A.N. approach, what

357
00:24:23,870 --> 00:24:26,180
we are doing, we are just trading in one direction.

358
00:24:26,450 --> 00:24:29,420
So that's where the time complexity is big often.

359
00:24:30,850 --> 00:24:33,490
So what we are using here, so basically.

360
00:24:36,360 --> 00:24:44,070
So in the third approach, what we are using, I am creating our data to store our results so it will

361
00:24:44,070 --> 00:24:49,920
see carefully, we can also solve this question with the help of three variables, with the help of

362
00:24:49,920 --> 00:24:50,520
three variables.

363
00:24:50,520 --> 00:24:57,810
And we do not need this any white variables because it will say carefully selected for filling out any

364
00:24:57,810 --> 00:24:58,260
entry.

365
00:24:59,130 --> 00:25:00,740
Suppose you want to fill this entry.

366
00:25:00,930 --> 00:25:01,710
What do you want?

367
00:25:01,740 --> 00:25:05,090
You want the previous entry and previous of previous entry.

368
00:25:05,370 --> 00:25:06,090
So what will do?

369
00:25:06,090 --> 00:25:07,760
I will take one variable for this one.

370
00:25:07,770 --> 00:25:11,000
I will take one variable for this one and I will take one variable for this one.

371
00:25:11,370 --> 00:25:16,650
So instead of keeping instead of using this area, we can also use three variables to solve this problem.

372
00:25:17,490 --> 00:25:19,890
So then our space complexity will become an.

373
00:25:20,820 --> 00:25:23,850
If I'm using one day, I read in the space complexities big often.

374
00:25:24,850 --> 00:25:31,300
But what if we lose, we will use aerially because in many problems, we cannot optimize space.

375
00:25:31,600 --> 00:25:34,150
So that's why I make a habit of using it.

376
00:25:35,410 --> 00:25:36,910
So what we are doing here?

377
00:25:38,860 --> 00:25:40,170
Let's analyze our problem.

378
00:25:40,320 --> 00:25:48,650
So what do we have so I have a problem I have and so this is my bigger problem and what this bigger

379
00:25:48,660 --> 00:25:53,240
problem is doing, it is calling on two small problems to solve the problems.

380
00:25:53,790 --> 00:25:57,540
So these are two suburb problems and minus one and and minus two.

381
00:25:58,110 --> 00:26:01,290
And these problems will again do some work.

382
00:26:01,560 --> 00:26:08,760
And this problem will also do some work and as soon as discussed these two problems.

383
00:26:09,900 --> 00:26:11,270
Have some common book.

384
00:26:12,510 --> 00:26:15,750
These two problems have some common work between them.

385
00:26:16,710 --> 00:26:22,720
And what we are doing here, we are using an Eddie to avoid common.

386
00:26:23,430 --> 00:26:24,210
So what we will do?

387
00:26:24,240 --> 00:26:25,740
We will avoid the common vogue.

388
00:26:27,150 --> 00:26:33,900
How can we avoid the common work we will store, that is so we will store and reuse.

389
00:26:35,860 --> 00:26:41,970
Suppose there is some work and this work is also presented, so they will do the work and we will store

390
00:26:41,970 --> 00:26:42,430
it here.

391
00:26:43,260 --> 00:26:44,740
So then we will reach here.

392
00:26:44,790 --> 00:26:47,720
We will likely return the result instead of doing the calculation.

393
00:26:48,120 --> 00:26:52,560
So I'm avoiding the common work which is done by both these problems.

394
00:26:53,070 --> 00:26:57,360
The work will be done only once and restored and we will reuse.

395
00:26:57,390 --> 00:26:58,470
So this concept.

396
00:27:00,560 --> 00:27:02,690
This concept is called dynamic programming.

397
00:27:04,340 --> 00:27:04,930
Understood.

398
00:27:05,180 --> 00:27:11,040
So what we will do so in the next few days, we will sell some more caution using the programming.

399
00:27:11,300 --> 00:27:15,620
So I hope you understand the programming programming, any programming store and reuse.

400
00:27:15,620 --> 00:27:21,430
Do not repeat yourself or do the work only once, store the result and use the result for future use.

401
00:27:21,830 --> 00:27:24,680
Simple, I will tune the next one by.