- Home/
- GATE ELECTRONICS/
- GATE EC/
- Article
Difference Between Greedy Method and Dynamic Programming
By BYJU'S Exam Prep
Updated on: September 25th, 2023
Difference Between Greedy Method and Dynamic Programming: In dynamic programming, various techniques are used to solve optimization problems. The greedy method and dynamic programming are those techniques used for problem optimization. The major difference between the greedy method and dynamic programming is that dynamic programming always provides the optimal solution whereas the greedy method might not provide the optimal solution every time.
Here, we will first explore the greedy method and dynamic programming in brief thereafter we will see the difference between the Greedy method and dynamic programming based on various factors such as feasibility, optimality, recursion, etc.
Table of content
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:
