Solutions to problems using dynamic programming or greedy methods?

Question

What properties should the problem have so that I can decide which method to use dynamic programming or greedy method?

Answer 1

Dynamic programming problems exhibit optimal substructure. This means that the solution to the problem can be expressed as a function of solutions to subproblems that are strictly smaller.

One example of such a problem is matrix chain multiplication.

Greedy algorithms can be used only when a locally optimal choice leads to a totally optimal solution. This can be harder to see right away, but generally easier to implement because you only have one thing to consider (the greedy choice) instead of multiple (the solutions to all smaller subproblems).

One famous greedy algorithm is Kruskal's algorithm for finding a minimum spanning tree.