DEV Community

Susritha09
Susritha09

Posted on

2

Dynamic Programming Vs Greedy

Dynamic Programming:

It just solves problems by combining the sub problems to solutions only of the sub problems were independent.
It can be used for solving both mathematical optimization method and computer programming method.
For example, it can be used for finding the shortest path in graph.
• Many decision sequence may be generated.
• Highly reliable
• Bottom-up approach
• There is no special set of feasible solution
• Less Efficiency
• Overlapping subproblems choose feasible solution

Alt Text


The algorithm used is:

Alt Text

Greedy Method:

Greedy method solves problems step by step which leads to global optimization solution.
• Generates a single decision sequence
• Less reliable
• Top to bottom approach
• Contain a special set of feasible set of solutions.
• More efficiency
• Overlapping subproblems cannot be handled.

Alt Text
Algorithm for greedy is:
Greedy(D,n)
//In Greedy approach D is domain
//from which solution is to be obtained of size n
//Initially assume
solution<-0
for i<-1 to n do{
s<-select(D)
if(Feasible solution,s))then
Solution<-Union(Solution,s)
}
return solution

Retry later

Top comments (0)

👋 Kindness is contagious

Engage with a wealth of insights in this thoughtful article, valued within the supportive DEV Community. Coders of every background are welcome to join in and add to our collective wisdom.

A sincere "thank you" often brightens someone’s day. Share your gratitude in the comments below!

On DEV, the act of sharing knowledge eases our journey and fortifies our community ties. Found value in this? A quick thank you to the author can make a significant impact.

Okay