1
00:00:00,170 --> 00:00:02,330
Hey there and welcome back!

2
00:00:02,330 --> 00:00:08,510
So far we have discussed recursion and we have also thoroughly discussed backtracking.

3
00:00:08,750 --> 00:00:15,710
Let's now get started with another algorithmic approach called dynamic programming.

4
00:00:15,740 --> 00:00:24,470
Now dynamic programming can be used to solve many problems that can be solved with recursion in a better

5
00:00:24,470 --> 00:00:25,070
manner.

6
00:00:25,070 --> 00:00:27,470
Now for this, let's take an example.

7
00:00:27,470 --> 00:00:33,980
Let's take the question where we are asked to identify the nth Fibonacci number.

8
00:00:33,980 --> 00:00:42,500
Now the Fibonacci series has the relation that f of n is equal to f of n minus one plus f of n minus

9
00:00:42,500 --> 00:00:42,890
two.

10
00:00:42,890 --> 00:00:46,850
Now we will see this in greater detail in a future video.

11
00:00:46,850 --> 00:00:53,780
But over here, let's just use it to develop an intuition regarding why dynamic programming is better

12
00:00:53,780 --> 00:00:58,310
than just plain simple recursion in many coding interview questions.

13
00:00:58,310 --> 00:01:06,200
So for the Fibonacci series, f of n is equal to f of n minus one plus f of n minus two.

14
00:01:06,200 --> 00:01:14,870
And it's also given that in this series, the first term or the zeroth term is zero, and the next term

15
00:01:14,870 --> 00:01:15,590
is one.

16
00:01:15,590 --> 00:01:18,440
So we have zero and then we have one.

17
00:01:18,440 --> 00:01:25,040
And then notice over here f of n is equal to f of n minus one plus f of n minus two.

18
00:01:25,040 --> 00:01:29,750
So the next term would be the sum of the previous two terms.

19
00:01:29,750 --> 00:01:33,110
So over here we would get zero plus one which is one.

20
00:01:33,110 --> 00:01:36,470
And then the next term would be the sum of these two terms.

21
00:01:36,470 --> 00:01:38,960
So one plus one is equal to two.

22
00:01:38,960 --> 00:01:42,680
And then we'll have three because one plus two is three.

23
00:01:42,680 --> 00:01:46,280
And the next term would be five because two plus three is five.

24
00:01:46,280 --> 00:01:49,490
And then we'll have eight because three plus five is eight.

25
00:01:49,490 --> 00:01:51,980
And it goes on in this manner.

26
00:01:52,310 --> 00:01:59,780
Now imagine that we have written a recursive solution to find the nth Fibonacci number.

27
00:01:59,780 --> 00:02:02,480
Let's say n is equal to five.

28
00:02:02,480 --> 00:02:03,830
Now f of five.

29
00:02:03,830 --> 00:02:05,090
Let's say that's what we want.

30
00:02:05,090 --> 00:02:11,390
So f of zero is zero, f of one is one, f of two is one, f of three is two.

31
00:02:11,390 --> 00:02:14,570
And notice over here f of five is five.

32
00:02:14,570 --> 00:02:19,190
So we are going to write a recursive function to find f of n.

33
00:02:19,190 --> 00:02:24,890
So for that let's first draw the recursive tree of the solution that we could write.

34
00:02:24,890 --> 00:02:29,090
And for simplicity sake let's just take n to be equal to five.

35
00:02:29,090 --> 00:02:31,850
So we want to find f of five.

36
00:02:32,370 --> 00:02:39,300
And because f of five is equal to f of four plus f of three, we would have to recursively call the

37
00:02:39,300 --> 00:02:42,750
function that finds this with a smaller input.

38
00:02:42,750 --> 00:02:45,900
So we would have to call f of four and f of three.

39
00:02:46,140 --> 00:02:52,320
Now to find f of four, we would have to recursively call f of three and f of two.

40
00:02:52,350 --> 00:02:58,530
Similarly, to find f of three, we would have to call f of two and f of one for f of two.

41
00:02:58,560 --> 00:03:01,380
We would have to call f of one and f of zero.

42
00:03:01,590 --> 00:03:03,990
Now over here we have f of two.

43
00:03:04,020 --> 00:03:08,850
For this again we would have to call f of one and f of zero.

44
00:03:09,240 --> 00:03:11,190
And over here we have f of three.

45
00:03:11,190 --> 00:03:14,370
So for that we would have to call f of two and f of one.

46
00:03:14,370 --> 00:03:19,470
And for finding f of two again we would have to call f of one and f of zero.

47
00:03:19,500 --> 00:03:22,830
Now again this would be the recursive solution that we would write.

48
00:03:22,830 --> 00:03:28,950
And we can stop when we hit the base case where n is either 0 or 1, because we know f of zero is zero

49
00:03:28,950 --> 00:03:30,540
and f of one is one.

50
00:03:30,540 --> 00:03:32,490
So these two would be returning.

51
00:03:32,490 --> 00:03:35,160
So f of one will return, f of zero will return.

52
00:03:35,160 --> 00:03:37,170
And we would find the value of f of two.

53
00:03:37,170 --> 00:03:38,910
And this would return to f of three.

54
00:03:38,910 --> 00:03:41,160
And it would go on in that manner.

55
00:03:41,190 --> 00:03:50,070
Now notice over here in this simple recursive approach we are calculating for example f of three two

56
00:03:50,070 --> 00:03:55,590
times f of two is being calculated over here and over here and over here.

57
00:03:55,590 --> 00:04:00,900
So notice that we are calculating the same f of n multiple times.

58
00:04:00,900 --> 00:04:07,140
For example, f of three is calculated twice, f of two is calculated thrice, etc..

59
00:04:07,170 --> 00:04:11,520
Now this is where dynamic programming becomes quite handy.

60
00:04:11,550 --> 00:04:19,350
Now instead of calculating this again and again, why don't we just store it to avoid the recomputing?

61
00:04:19,350 --> 00:04:26,010
Now this over here is dynamic programming or it is one approach in dynamic programming.

62
00:04:26,010 --> 00:04:30,570
So dynamic programming is just recursion plus storage.

63
00:04:30,570 --> 00:04:37,080
Now again this is one of the approaches of dynamic programming which is what we call memoization.

64
00:04:37,080 --> 00:04:42,450
So memoization is just writing the normal recursive solution.

65
00:04:42,450 --> 00:04:47,220
But then when we find something that's useful later we will just store it.

66
00:04:47,220 --> 00:04:51,720
So when we come to this branch, we would not go all the way over here.

67
00:04:51,720 --> 00:04:57,420
We would just directly return the value of f of three, because we have already calculated and stored

68
00:04:57,420 --> 00:04:59,040
it at this instance.

69
00:04:59,040 --> 00:05:06,510
So this is what we call memoization, and it is the first approach that we will discuss in dynamic programming.

70
00:05:06,870 --> 00:05:12,720
The second approach that we will discuss in dynamic programming is what is called tabulation.

71
00:05:12,720 --> 00:05:19,500
Now just to develop an intuition about this, again, let's take a look at the Fibonacci series question.

72
00:05:19,500 --> 00:05:27,300
Notice over here that to find f of five we had to ultimately find f of four, f of three, and f of

73
00:05:27,300 --> 00:05:31,800
two, and again f of one and f of zero is something that we already know.

74
00:05:31,800 --> 00:05:35,880
Now what if we had a table that looked something like this.

75
00:05:35,880 --> 00:05:41,910
And again, this is called tabulation for that particular reason that we would be using tables when

76
00:05:41,910 --> 00:05:43,260
we're discussing this approach.

77
00:05:43,260 --> 00:05:50,010
So what if we had a table over here and let's say the indices went from zero right up to five.

78
00:05:52,120 --> 00:05:59,770
And then to find F of five, we would just go ahead and find f of two, f of three, f of four, and

79
00:05:59,770 --> 00:06:01,990
then proceed and find f of five.

80
00:06:01,990 --> 00:06:05,560
So this approach is what we call tabulation.

81
00:06:05,560 --> 00:06:11,680
Now we will discuss these two approaches in much greater detail in future videos.

82
00:06:11,680 --> 00:06:16,060
But over here we're just trying to get introduced to dynamic programming.

83
00:06:16,060 --> 00:06:22,900
And we have built a good intuition about why dynamic programming is a very efficient way of solving

84
00:06:22,900 --> 00:06:23,230
coding.

85
00:06:23,230 --> 00:06:24,100
Interview questions.

86
00:06:24,100 --> 00:06:30,070
So the two dynamic programming approaches that we have discussed over here are memoization, which is

87
00:06:30,070 --> 00:06:35,260
basically recursion plus storage and tabulation, which is using a table.

88
00:06:35,260 --> 00:06:40,300
And then we would just find values to find the final solution that we want to find.

89
00:06:40,330 --> 00:06:46,750
Notice that in tabulation as well we are not calculating these values multiple times, but rather we

90
00:06:46,750 --> 00:06:48,400
are just calculating it once.

91
00:06:48,400 --> 00:06:50,770
So f of two is calculated only once.

92
00:06:50,770 --> 00:06:56,200
F of three is only calculated once, and f of four is also only calculated once and again.

93
00:06:56,200 --> 00:07:02,380
Whenever we calculate these values, we store them over here, and we use these values to find the answer

94
00:07:02,380 --> 00:07:04,150
that is asked of us.

95
00:07:04,150 --> 00:07:07,780
So what is basically dynamic programming?

96
00:07:07,810 --> 00:07:16,930
Dynamic programming is basically a method to solve complex problems, where problems exhibit two characteristics

97
00:07:16,930 --> 00:07:22,030
which are overlapping subproblems and optimal substructure.

98
00:07:22,030 --> 00:07:26,470
Now let's again take a look at the Fibonacci series question.

99
00:07:26,470 --> 00:07:29,920
And let's try to understand these two terms over here.

100
00:07:30,280 --> 00:07:33,580
The first term is overlapping subproblems.

101
00:07:33,580 --> 00:07:40,210
And we have seen that we were calculating f of three multiple times and f of two multiple times.

102
00:07:40,210 --> 00:07:44,110
So this is what we call overlapping subproblems.

103
00:07:44,110 --> 00:07:50,500
And to make this process efficient we discussed that we would just store these values when we compute

104
00:07:50,500 --> 00:07:50,890
them.

105
00:07:50,890 --> 00:07:55,840
And in that manner we can avoid recomputing them again and again.

106
00:07:55,840 --> 00:08:02,920
So the first characteristic of dynamic programming questions is that there would be overlapping subproblems.

107
00:08:02,920 --> 00:08:10,390
And hence, by just making the slight tweak of storing things that we compute, we will be able to significantly

108
00:08:10,390 --> 00:08:12,130
improve the time complexity.

109
00:08:12,130 --> 00:08:19,690
The second characteristic of problems which can be solved using dynamic programming is that they will

110
00:08:19,690 --> 00:08:22,060
exhibit optimal substructure.

111
00:08:22,060 --> 00:08:25,840
Now what do we mean with optimal substructure?

112
00:08:25,840 --> 00:08:35,920
Optimal substructure means that solutions to a problem can be constructed from optimal solutions of

113
00:08:35,920 --> 00:08:37,330
its subproblem.

114
00:08:37,330 --> 00:08:39,400
Now what does this mean over here?

115
00:08:39,400 --> 00:08:47,560
Now, in the case of the Fibonacci question, notice that to find f of five, for example, we can just

116
00:08:47,560 --> 00:08:51,550
find f of four and f of three, which are subproblems.

117
00:08:51,550 --> 00:08:59,650
And these solutions can be used as it is by just adding these two together to find the value of f of

118
00:08:59,650 --> 00:09:00,130
five.

119
00:09:00,130 --> 00:09:06,100
So in this case optimal solutions to the subproblems which are.

120
00:09:06,100 --> 00:09:13,330
These two over here were used to find the optimal solution of the problem which is f of five.

121
00:09:13,330 --> 00:09:16,570
So this is what we call optimal substructure.

122
00:09:16,570 --> 00:09:24,070
Now let's quickly take a case where a coding interview question can be solved with recursion, but cannot

123
00:09:24,070 --> 00:09:29,980
be solved with dynamic programming because the problem does not have optimal substructure.

124
00:09:29,980 --> 00:09:36,760
To just thoroughly understand this now, we have seen that the Fibonacci question has optimal substructure,

125
00:09:36,760 --> 00:09:38,560
and that's what we have just now discussed.

126
00:09:38,560 --> 00:09:45,670
But a question which does not have optimal substructure is, for example, the Tower of Hanoi problem,

127
00:09:45,670 --> 00:09:48,490
which we had discussed under recursion.

128
00:09:48,490 --> 00:09:56,680
Now in the Tower of Hanoi problem, we had three rods and we had to move the given number of disks,

129
00:09:56,680 --> 00:10:04,090
the n number of disks from the first rod to the last rod, and we could take the help of an auxiliary

130
00:10:04,090 --> 00:10:04,540
rod.

131
00:10:04,540 --> 00:10:10,600
Now, the conditions were that you could not place a bigger disk on a smaller disk, and you can just

132
00:10:10,600 --> 00:10:12,190
move one disk at a time.

133
00:10:12,190 --> 00:10:19,690
Now in this question, remember what we discussed was that we would first move n minus one disks from

134
00:10:19,690 --> 00:10:22,450
rod number one to rod number two.

135
00:10:23,150 --> 00:10:29,540
And then we would move the biggest disk over here from rod one to rod three.

136
00:10:29,540 --> 00:10:35,480
And then finally we would move n minus one disks from rod two to rod three.

137
00:10:35,480 --> 00:10:39,440
So this is the approach that we have discussed for the Tower of Hanoi problem.

138
00:10:39,440 --> 00:10:49,460
Now notice over here solving n minus one disks problem or the sub problem is not used as it is for solving

139
00:10:49,460 --> 00:10:56,270
the problem where there are n disks, because if there had been n minus one disks, we would not be

140
00:10:56,270 --> 00:10:59,480
moving those n minus one disks to row two.

141
00:10:59,480 --> 00:11:05,990
But because we have n disks, we are moving n minus one disks from rod one to row two, and later we

142
00:11:05,990 --> 00:11:08,030
are moving them from here to here.

143
00:11:08,030 --> 00:11:15,500
But again notice the optimal solution of the sub problem is not used for solving the problem.

144
00:11:15,500 --> 00:11:18,260
So again that's the definition of optimal substructure.

145
00:11:18,260 --> 00:11:25,190
The optimal solution to a problem can be constructed from optimal solutions of its subproblems.

146
00:11:25,190 --> 00:11:31,850
Again notice over here if we had n minus one disks we would not move n minus one disks from rod one

147
00:11:31,850 --> 00:11:32,630
to rod two.

148
00:11:32,630 --> 00:11:39,440
Rather, we would move n minus two disks from rod one to row two, or rather one disk less than the

149
00:11:39,440 --> 00:11:40,610
total number of disks.

150
00:11:40,610 --> 00:11:46,250
So notice the optimal solution for the problem where we have n minus one.

151
00:11:46,250 --> 00:11:51,050
Disks cannot be used for solving the problem where we have n disks.

152
00:11:51,050 --> 00:11:57,470
We are using recursion to solve this problem, but we cannot use dynamic programming to solve the Tower

153
00:11:57,470 --> 00:11:59,690
of Hanoi problem because it does not.

154
00:11:59,690 --> 00:12:03,110
The problem does not exhibit optimal substructure.

155
00:12:03,110 --> 00:12:04,340
So quickly.

156
00:12:04,340 --> 00:12:11,120
Summarizing, we discussed the two approaches in dynamic programming that we would be discussing.

157
00:12:11,120 --> 00:12:19,790
The first one is recursion plus storage, which is what is called memoization, and the second approach

158
00:12:19,790 --> 00:12:21,260
is called tabulation.

159
00:12:23,660 --> 00:12:30,320
We also discussed that dynamic programming can be used in coding interview questions, where the problem

160
00:12:30,320 --> 00:12:32,330
exhibits two characteristics.

161
00:12:32,330 --> 00:12:40,670
The first characteristic is overlapping subproblems, and the second characteristic is optimal.

162
00:12:42,080 --> 00:12:43,220
Substructure.

163
00:12:47,490 --> 00:12:55,290
In the next video, let's discuss the approach that we will take in this course to master dynamic programming.