DP vs Greedy Algorithms
Both Dynamic Programming and Greedy are algorithmic paradigms used to solve optimization problems .
Greedy Approach deals with forming the solution step by step by choosing the local optimum at each step and finally reaching a global optimum. Therefore, Greedy Approach does not deal with multiple possible solutions, it just builds the one solution that it believes to be correct. In other words, the principle of Greedy is that we assume that choosing the local optimum at each stage will lead to form the global optimum.
Dynamic Programming(DP) does not deal with such kinds of uncertain assumptions. DP finds a solution to all subproblems and chooses the best ones to form the global optimum.
To read about each algorithmic paradigm, read these two blogs: What are Greedy Algorithms? and Idea of Dynamic Programming .
Dynamic Programming is guaranteed to reach the correct answer each and every time whereas Greedy is not.
This is because, in Dynamic Programming, we form the global optimum by choosing at each step depending on the solution of previous smaller subproblems whereas, in Greedy Approach, we consider the choice that seems the best at the moment.
Then why not use Dynamic Programming always?
We don’t use Dynamic Programming with all problems because Greedy is faster when it delivers the correct solution since it only deals with one subproblem. Also, Dynamic Programming works only when there are overlapping subproblems.
But how to choose between Greedy and DP?
Whenever an optimization problem has an optimal substructure property, we know that it might be solved with Greedy and DP. But how to choose between these two?
Well, if the problem holds the Greedy Choice Property, its best to solve it using the Greedy Approach.
And if it has overlapping subproblems, solve it with Dynamic Programming.
What if we can solve the problem using both Greedy and DP?
There are some problems that can be solved using both Greedy and DP like Coin Change Problems(can be solved using greedy for a certain type of input). In such cases, it is best to solve it using Greedy because it will be faster since it only solves one subproblem and DP solves multiple subproblems before reaching the final answer.
Conclusion
If an optimization problem has an optimal substructure, it may be solved using Greedy or Dynamic Programming. Now you need to look further for some other properties →
- If Greedy Choice Property holds for the problem, use the Greedy Approach. It will return the correct answer faster than DP.
- If Greedy Choice Property doesn’t hold and there are overlapping subproblems, use DP to find the correct answer
