Welcome back.
In the previous videos we have discussed what the greedy algorithm is.
We have also discussed what greedy algorithms are used for, which is basically for optimization problems.
And we have also seen that even though greedy algorithms are used for optimization problems, a greedy
algorithm does not guarantee to give an optimal solution for every problem, and therefore it would
imply that using a greedy algorithm is suitable only for a certain type of problems.
Now that brings us to the question that we're going to discuss in this video, which is what problems
are suitable for greedy algorithms.
Now, when you analyze problems that are suitable for greedy algorithms, you will see that these problems
have two properties.
The two properties that a problem needs to have are the greedy choice property and optimal substructure.
Now let's try to understand these two properties.
And then let's compare whether the two problems that we had previously discussed satisfy these two properties
or not.
So let's get started.
The first property is the greedy choice property.
This property says that the global optimum can be obtained by choosing local optimum at each step.
Okay, so that's the greedy choice property.
Now if a problem satisfies this then probably we can solve that problem with the greedy algorithm.
Now again more of that later.
And as we go ahead and discuss real coding interview questions, we'll also try to understand how those
problems satisfy the greedy choice property.
But more of that coming up soon.
Now what is the second property that problems suitable for greedy algorithms have?
The second property is optimal substructure, and with optimal substructure we mean that the optimal
solution to a problem contains within it the optimal solution to subproblems.
Or in other words, you can think of it in this manner that a problem can be broken down into smaller
related problems, such that the optimal solution to the overall problem can be constructed from the
optimal solution to its subproblems.
And again, this is something that we have discussed when we discussed dynamic programming as well.
So these are the two properties that indicate that a problem can be solved using a greedy algorithm
okay.
All right.
Now in the next video let's go ahead and come to the final topic in this section, which is to compare
the greedy approach with dynamic programming.