1
00:00:00,170 --> 00:00:01,220
Welcome back.

2
00:00:01,220 --> 00:00:06,740
In this video, let's try to compare the greedy approach with dynamic programming.

3
00:00:06,740 --> 00:00:13,520
Now previously when we discussed what greedy algorithms are used for, we had seen that they are used

4
00:00:13,520 --> 00:00:15,830
for optimization problems.

5
00:00:15,830 --> 00:00:22,370
And you're well aware that dynamic programming is also used for optimization problems.

6
00:00:22,370 --> 00:00:27,740
We have discussed that in detail when we covered dynamic programming in previous videos.

7
00:00:27,740 --> 00:00:34,370
So both the greedy approach as well as dynamic programming are used for optimization problems.

8
00:00:34,370 --> 00:00:41,780
Now, that's why it's important to compare between these two approaches and to try to really grasp the

9
00:00:41,780 --> 00:00:43,280
difference between these two.

10
00:00:43,280 --> 00:00:45,440
So let's go ahead and do that.

11
00:00:45,440 --> 00:00:52,010
And for comparing the greedy approach with dynamic programming, let's use these four parameters.

12
00:00:52,010 --> 00:00:59,150
Now when it comes to the core strategy, the greedy algorithm as you've seen previously, is all about

13
00:00:59,150 --> 00:01:07,490
making locally optimal solutions or choices at each step, hoping to get to the global optimal solution.

14
00:01:07,490 --> 00:01:14,960
Now, when it comes to dynamic programming, the core strategy is breaking the problem into subproblems

15
00:01:14,960 --> 00:01:18,530
and then solving the subproblems to solve the problem.

16
00:01:18,530 --> 00:01:25,070
So that's the difference in the core strategy that's being used in these two approaches.

17
00:01:25,130 --> 00:01:32,030
Now, when it comes to the approach, the main difference between the greedy algorithm and dynamic programming

18
00:01:32,030 --> 00:01:40,220
is that the greedy algorithm does not reconsider its choices, but then dynamic programming considers

19
00:01:40,220 --> 00:01:44,330
all possible paths or solutions for solving a problem.

20
00:01:44,330 --> 00:01:48,170
So dynamic programming is more exhaustive in nature.

21
00:01:48,170 --> 00:01:55,700
The third parameter which I have over here is table, and in this respect, the greedy algorithms do

22
00:01:55,700 --> 00:02:04,070
not use any table to store anything, but dynamic programming uses a table to store solutions to subproblems,

23
00:02:04,070 --> 00:02:07,790
so that those solutions can be used to solve the problem at hand.

24
00:02:07,790 --> 00:02:14,750
And finally, when it comes to the time complexity, typically greedy algorithms are more efficient

25
00:02:14,750 --> 00:02:20,990
than dynamic programming algorithms, which are typically slower in nature because they are exhaustive

26
00:02:20,990 --> 00:02:21,710
in nature.

27
00:02:21,740 --> 00:02:28,220
Okay, so the greedy algorithms are typically simpler and easy to implement and more efficient.

28
00:02:28,220 --> 00:02:34,610
Okay, so we have discussed the difference between the greedy approach and dynamic programming based

29
00:02:34,610 --> 00:02:36,740
on these four parameters.

30
00:02:36,740 --> 00:02:43,280
Now, to solidify our understanding and the difference between these two, let's consider a few coding

31
00:02:43,280 --> 00:02:46,670
interview problems categorized into three categories.

32
00:02:46,670 --> 00:02:53,990
The first category is coding interview problems that can be solved both using a greedy approach as well

33
00:02:53,990 --> 00:02:55,520
as dynamic programming.

34
00:02:55,520 --> 00:03:01,070
Under the second category, over here, we list down a few coding interview problems that can be solved

35
00:03:01,070 --> 00:03:05,000
using a greedy approach, but cannot be solved using dynamic programming.

36
00:03:05,000 --> 00:03:10,250
And finally, we have the third category, under which we will list a few coding interview questions

37
00:03:10,250 --> 00:03:15,830
that cannot be solved using a greedy approach, but can be solved using dynamic programming.

38
00:03:15,830 --> 00:03:17,240
So let's get started.

39
00:03:17,240 --> 00:03:23,060
Now when it comes to the first category over here, notice these problems or the problems that we're

40
00:03:23,060 --> 00:03:29,210
going to list over here, can be solved using both a greedy approach as well as dynamic programming.

41
00:03:29,210 --> 00:03:35,450
And when you have a scenario like this, typically solving the problem using a greedy approach will

42
00:03:35,450 --> 00:03:37,490
give you a better time complexity.

43
00:03:37,490 --> 00:03:43,430
So these are a few problems which can be solved using the greedy approach as well as dynamic programming.

44
00:03:43,430 --> 00:03:44,660
So you have jump game.

45
00:03:44,660 --> 00:03:46,970
You have best time to buy and sell stocks.

46
00:03:46,970 --> 00:03:49,550
You have two city scheduling, etc..

47
00:03:49,550 --> 00:03:54,920
Okay, there are many problems now when it comes to the second category, which are problems that can

48
00:03:54,920 --> 00:03:59,330
be solved using the greedy approach, but cannot be solved using dynamic programming.

49
00:03:59,330 --> 00:04:06,830
The reason for this typically is that such problems do not have overlapping subproblems.

50
00:04:06,830 --> 00:04:12,320
Okay, remember problems that can be solved using greedy approach as well as dynamic programming approach.

51
00:04:12,320 --> 00:04:14,540
Both have optimal substructure.

52
00:04:14,540 --> 00:04:20,420
So the difference over here is that overlapping subproblems are not there, because of which probably

53
00:04:20,420 --> 00:04:23,030
we are not able to use dynamic programming.

54
00:04:23,030 --> 00:04:30,500
Now, a few such examples are the fractional knapsack problem, gas stations, and the task scheduler

55
00:04:30,500 --> 00:04:31,190
problem.

56
00:04:31,190 --> 00:04:35,720
And when it comes to the third category, which are problems that cannot be solved using the greedy

57
00:04:35,720 --> 00:04:38,360
approach, but can be solved using dynamic programming.

58
00:04:38,360 --> 00:04:44,000
And the reason for this typically is that the problems do not follow the greedy choice property.

59
00:04:44,000 --> 00:04:50,990
Okay, so a few examples for this category are the longest increasing subsequence problem, word break

60
00:04:50,990 --> 00:04:52,190
and edit distance.

61
00:04:52,190 --> 00:04:52,580
Okay.

62
00:04:52,580 --> 00:04:57,140
And all of these are problems that we have previously discussed under dynamic programming.

63
00:04:57,140 --> 00:04:59,630
And you will see that for these problems.

64
00:04:59,860 --> 00:05:03,010
We need to consider all possible solutions.

65
00:05:03,010 --> 00:05:07,180
And again, that's something that the greedy algorithms do not do.

66
00:05:07,210 --> 00:05:07,690
Okay.

67
00:05:07,690 --> 00:05:12,820
Now again, you can try to think of these problems to really understand the difference between these

68
00:05:12,820 --> 00:05:14,560
and in the subsequent videos.

69
00:05:14,560 --> 00:05:19,870
With more practice, you will become better and better at using greedy algorithms.

70
00:05:19,870 --> 00:05:23,020
So let's get started with coding interview questions.