Welcome back.
In this video, let's try to compare the greedy approach with dynamic programming.
Now previously when we discussed what greedy algorithms are used for, we had seen that they are used
for optimization problems.
And you're well aware that dynamic programming is also used for optimization problems.
We have discussed that in detail when we covered dynamic programming in previous videos.
So both the greedy approach as well as dynamic programming are used for optimization problems.
Now, that's why it's important to compare between these two approaches and to try to really grasp the
difference between these two.
So let's go ahead and do that.
And for comparing the greedy approach with dynamic programming, let's use these four parameters.
Now when it comes to the core strategy, the greedy algorithm as you've seen previously, is all about
making locally optimal solutions or choices at each step, hoping to get to the global optimal solution.
Now, when it comes to dynamic programming, the core strategy is breaking the problem into subproblems
and then solving the subproblems to solve the problem.
So that's the difference in the core strategy that's being used in these two approaches.
Now, when it comes to the approach, the main difference between the greedy algorithm and dynamic programming
is that the greedy algorithm does not reconsider its choices, but then dynamic programming considers
all possible paths or solutions for solving a problem.
So dynamic programming is more exhaustive in nature.
The third parameter which I have over here is table, and in this respect, the greedy algorithms do
not use any table to store anything, but dynamic programming uses a table to store solutions to subproblems,
so that those solutions can be used to solve the problem at hand.
And finally, when it comes to the time complexity, typically greedy algorithms are more efficient
than dynamic programming algorithms, which are typically slower in nature because they are exhaustive
in nature.
Okay, so the greedy algorithms are typically simpler and easy to implement and more efficient.
Okay, so we have discussed the difference between the greedy approach and dynamic programming based
on these four parameters.
Now, to solidify our understanding and the difference between these two, let's consider a few coding
interview problems categorized into three categories.
The first category is coding interview problems that can be solved both using a greedy approach as well
as dynamic programming.
Under the second category, over here, we list down a few coding interview problems that can be solved
using a greedy approach, but cannot be solved using dynamic programming.
And finally, we have the third category, under which we will list a few coding interview questions
that cannot be solved using a greedy approach, but can be solved using dynamic programming.
So let's get started.
Now when it comes to the first category over here, notice these problems or the problems that we're
going to list over here, can be solved using both a greedy approach as well as dynamic programming.
And when you have a scenario like this, typically solving the problem using a greedy approach will
give you a better time complexity.
So these are a few problems which can be solved using the greedy approach as well as dynamic programming.
So you have jump game.
You have best time to buy and sell stocks.
You have two city scheduling, etc..
Okay, there are many problems now when it comes to the second category, which are problems that can
be solved using the greedy approach, but cannot be solved using dynamic programming.
The reason for this typically is that such problems do not have overlapping subproblems.
Okay, remember problems that can be solved using greedy approach as well as dynamic programming approach.
Both have optimal substructure.
So the difference over here is that overlapping subproblems are not there, because of which probably
we are not able to use dynamic programming.
Now, a few such examples are the fractional knapsack problem, gas stations, and the task scheduler
problem.
And when it comes to the third category, which are problems that cannot be solved using the greedy
approach, but can be solved using dynamic programming.
And the reason for this typically is that the problems do not follow the greedy choice property.
Okay, so a few examples for this category are the longest increasing subsequence problem, word break
and edit distance.
Okay.
And all of these are problems that we have previously discussed under dynamic programming.
And you will see that for these problems.
We need to consider all possible solutions.
And again, that's something that the greedy algorithms do not do.
Okay.
Now again, you can try to think of these problems to really understand the difference between these
and in the subsequent videos.
With more practice, you will become better and better at using greedy algorithms.
So let's get started with coding interview questions.