Before learning about greedy method and dynamic programming, let us know why and where these methods are required.
The answer is optimisation problems.
Optimisation problems are required when we want to know the extremes of the results, that is, either maximum results or minimum results.
Greedy method of solving problems involves a predefined procedure to follow to obtain the result.
For example, if you want to do maximum number of jobs in a fixed time, then you only have one optimal predefined approach, and that is to start from shortest time taking job followed by the next shortest. Basically you have to move in ascending order in terms of time.
Note – WE CANNOT HAVE OPTIMAL GREEDY METHODS FOR EVERY PROBLEM.
Dynamic Programming involves trying all procedures and scenarios and then picking up the most optimal approach among them.
As the method suggest, it is definitely slower than the greedy method but most efficient and can be found for every problem.
There are two approaches in dynamic programming, recursive and iterative out of which we generally use the iterative approach.
I hope now you must have got some idea about the Greedy method and dynamic programming. We’ll talk about them in detail in upcoming posts.