2 min read

Difference between Greedy approach vs Dynamic programming

A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment whereas Dynamic Programming is guaranteed to reach the correct answer each and every time. Both are algorithmic paradigms used to solve optimization problems.
Difference between Greedy approach vs Dynamic programming

A Greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.

So the problems where choosing locally optimal also leads to a global solution are best fit for Greedy.

For example- Fractional Knapsack Problem.

Dynamic programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later.

For example- recursive solution for Fibonacci Numbers

FeatureGreedy methodDynamic programming
FeasibilityIn a greedy Algorithm, we make whatever choice seems best at the moment in the hope that it will lead to global optimal solution.In Dynamic Programming we make decision at each step considering current problem and solution to previously solved sub problem to calculate optimal solution .
OptimalityIn Greedy Method, sometimes there is no such guarantee of getting Optimal Solution.It is guaranteed that Dynamic Programming will generate an optimal solution as it generally considers all possible cases and then choose the best.
RecursionA greedy method follows the problem solving heuristic of making the locally optimal choice at each stage.A Dynamic programming is an algorithmic technique which is usually based on a recurrent formula that uses some previously calculated states.
MemoizationIt is more efficient in terms of memory as it never look back or revise previous choicesIt requires dp table for memoization and it increases it’s memory complexity.
Time complexityGreedy methods are generally faster. For example, Dijkstra’s shortest path algorithm takes O(ELogV + VLogV) time.Dynamic Programming is generally slower. For example, Bellman Ford algorithm takes O(VE) time.
FashionThe greedy method computes its solution by making its choices in a serial forward fashion, never looking back or revising previous choices.Dynamic programming computes its solution bottom up or top down by synthesizing them from smaller optimal sub solutions.
ExampleFractional knapsack . 
 
0/1 knapsack problem 
Greedy approach vs Dynamic programming - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
https://www.geeksforgeeks.org/greedy-approach-vs-dynamic-programming/

#GreedyApproach #DynamicProgramming #Algorithm #Programming #Probyto #ProbytoAI

Subscribe and follow us for latest news in Data Science and Machine learning and stay updated!
Facebook: https://facebook.com/probyto
Twitter: https://twitter.com/probyto
LinkedIn: https://linkedin.com/company/probyto
Instagram: https://instagram.com/probyto