Can every optimization problem that can be solved by a greedy algorithm be solved using dynamic programming? Why, why not?

Question

In other terms, is the set of optimization problems solvable using greedy algorithms contained fully within the set of optimization problems solvable by dynamic programming?

Answer 1

The answer is yes in a rather trivial way: a locally optimal choice made by the greed approach is one of subproblems that would be considered by the dynamic programming approach.

However this does not entail that you should always use the dynamic programming approach because it may be inherently less efficient. For example, when you solve the shortest path problem in a graph, the dynamic programming approach necessarily implies solving it for all nodes as source. For this problem dynamic programming is thus less efficient (cubic time) than solving it only for two nodes (quadratic time—I'm assuming you just derive the straightforward algorithm, not using Fibonacci heaps.)