| 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 |
1 answer
Best answer
Was this answer helpful?
Thanks for the feedback.
Sign up free to save answers and ask your own doubts
Your answer
Log in or create a free account to answer this question.