Question

Write the difference between greedy method and dynamic programming

Answer 1

Greedy method	Dynamic programming
Does not guarantee an optimal solution	Guarantees an optimal solution
Assumes sub-problems do not overlap	Assumes sub-problems overlap
Does little work	Does more work
Only considers current choices	Considers future choices
Constructs the solution from a set of feasible choices	There is no specialized set of feasible choices
Selects a locally optimum choice	Selects globally optimum choices
No concept of memorization	Employs memorization
Examples: Knapsack, Job scheduling with deadlines, Kruskal, Prim’s	Examples: All pair shortest path, 0/1 Knapsack, Travelling salesman problem, LCS