Difference Between Greedy Method and Dynamic Programming
The greedy method is not as reliable as the Dynamic programming. There are various differences between the two methods which will help us understand which method to choose for our solution based on the type of problem:
Key Differences between Greedy and Dynamic Programming
|Greedy Method||Dynamic Programming|
|A single sequence of the decision is generated.||Various numbers of sequences of the decision are generated.|
|Not as reliable as Dynamic programming.||very reliable.|
|Follows serial forward approach.||Follows bottom-up or top-down approach.|
|An optimal solution may not be achieved.||The optimal solution is achieved every time.|
|Locally optimal choices are made on each step.||Uses already produced solutions of the previous steps to|
|Memory efficient.||Memory consumed more than the Greedy method.|
|Quicker results.||Slower results comparatively.|
|Example: Fractional knapsack problem.||Example: 0/1 knapsack problem.|
What is Greedy Method?
In order to solve or optimize a problem in dynamic programming, the Greedy method is widely used. It is an algorithm paradigm specially designed to have the optimal solution. In this algorithm paradigm, upcoming steps are chosen to provide immediate benefits.
This method is associated with the problems where the local optimal value will be chosen for the solution of the problem. The optimal solution may or may not be delivered by the Greedy method every time.
What is Dynamic Programming?
This method is also used to optimize a problem in dynamic programming. This method uses the pre-computed set for finding the solution from the already stored results. The speed of the processing is increased with this method but since the calculation is complex, this is a bit slower process than the Greedy method.
Dynamic programming always gives the optimal solution very quickly. This programming always makes a decision based on the in-hand problem. This programming uses the bottom-up or top-down approach.
Check out some important topics related to the in the table provided below: