Hi. In this video,

we will briefly review the main ingredients of greedy algorithms and

the first of them is reduction to a subproblem.

Basically, when you have some problem, you make some first move and

thus reduce your problem to a similar problem, but which is smaller.

For example, you have fewer digits left or fewer gas stations left in front of

you and this similar problem, which is smaller is called a subproblem.

Another key ingredient is a safe move and

the move is called safe if it is consistent with some optimal solution.

In other words, if there exists some optimal solution in which the first

move is the same as your move, then your move is called a safe move and

not all first moves are actually safe.

For example,

to go until there's no fuel is not a safe move in the problem about car fueling.

And often, greedy moves are also not safe, for example,

to get to the closest gas station and refuel at it is not a safe

move while to get to the farthest gas station and refuel there is a safe move.

Now the general strategy of solving a problem goes like this.

First, you analyze the problem and you come up with some greedy choice and

then the key thing is to prove that this greedy choice is a safe move and

you really have to prove it.

Because, otherwise, you can come up with some greedy choice and

then come up with a greedy algorithm and then even implement it and test it and

try to submit it in the system.

Only to learn that the algorithm is incorrect,

because the first move is actually not a safe move and there are cases in which

this first move is not consistent with any optimal solution.

And in that case, we will have to invent a new solution and

implement it from scratch.

All the work you've done before will be useless.

So please prove your algorithms and prove that the first move is a safe move.

When you prove that, you reduce a problem to a subproblem.

And hopefully, that is a similar problem, problem of a same kind and

then you start solving this subproblem the same way.

You make your greedy choice and you reduce it to subproblem, and

you iterate until there are no problems left or until your problem is so

simple that you can just solve it right away.

And in the next lessons,

we will apply greedy algorithms to solve more difficult problems.