Do dynamic programming and greedy algorithms solve the same type of problems?

Question

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically,

1. As far as I know, the type of problems that dynamic programming can solve are those that have "optimal structure". Can the same type of problems always be solved by greedy algorithms, either accurately or approximately? (I think yes)
2. Are there optimal problems that do not have "optimal structure" and can be solved by greedy algorithms, either accurately or approximately? If yes, what characterize the type of problems that can be solved by greedy algorithms, either accurately or approximately?

Thanks and regards!

Answer 1

("Approximately" is hard to define, so I'm only going to address the "accurately" or "optimally" aspect of your questions.)

There's a nice discussion of the difference between greedy algorithms and dynamic programming in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (Chapter 16, pages 381-383 in the second edition).

With respect to your first question, here's a summary of what they have to say. Both dynamic programming and greedy algorithms can be used on problems that exhibit "optimal substructure" (which CLRS defines by saying that an optimal solution to the problem contains within it optimal solutions to subproblems). However, in order for the greedy solution to be optimal, the problem must also exhibit what they call the "greedy-choice property"; i.e., a globally optimal solution can be arrived at by making locally optimal (greedy) choices. In contrast, dynamic programming is good for problems that exhibit not only optimal substructure but also overlapping subproblems. (This means that a particular subproblem can be reached in multiple ways. The dynamic programming algorithm calculates the value of each subproblem once and then can reuse these every time the algorithm revisits them.)

They then give the example of the 0-1 knapsack vs. the fractional knapsack problem here. Both exhibit the optimal substructure property, but only the second also exhibits the greedy-choice property. Thus the second one can be solved to optimality with a greedy algorithm (or a dynamic programming algorithm, although greedy would be faster), but the first one requires dynamic programming or some other non-greedy approach. See also Henry's example in the other answer.

It may also be helpful to read the following, which is the heart of their discussion of the difference and which I quote in full (emphasis mine):

In dynamic programming, we make a choice at each step, but the choice may depend on solutions to subproblems. In a greedy algorithm, we make whatever choice seems best at the moment and then solve the subproblems arising after the choice is made. The choice made by a greedy algorithm may depend on choices made so far, but it cannot depend on any future choices or on the solutions to subproblems. Thus, unlike dynamic programming, which solves the subproblems bottom up, a greedy strategy usually progresses in top-down fashion, making one greedy choice after another, iteratively reducing each given problem instance to a smaller one.

Basically, then, dynamic programming solves subproblems first and then uses the solutions to subproblems to construct solutions to larger problems. Greedy algorithms take on the entire larger problem first, and each greedy choice reduces the larger problem to a smaller subproblem. Thus the two kinds of algorithms are sort of inverses of each other.

---

With respect to your second question, here's another quote from CLRS (p. 380):

How can one tell if a greedy algorithm will solve a particular optimization problem? There is no way in general...

Answer 2

To answer your first question, there are problems which can be solved by dynamic programming but not satisfactorily by a greedy algorithm.

Take for example a Wikipedia example for finding a shortest path.

where the wavy lines have been calculated earlier by dynamic programming. The shortest overall path is clearly the top route, but a greedy algorithm would take the middle route since $2 < 5$. The values can be altered so that the greedy solution is not remotely close to the result from dynamic programming.

Answer 3

I don't know how to put this formally, but when a problem has the notion of feasibility, it may be that a greedy algorithm will be unable to find a feasible solution. In your path example, the greedy algorithm could lead you into a dead end, or perhaps (not sure) an endless loop.