How is dynamic programming different from greedy a

Question

In the book I am using Introduction to the Design & Analysis of Algorithms, dynamic programming is said to focus on the Principle of Optimality, "An optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances".

Whereas, the greedy technique focuses on expanding partially constructed solutions until you arrive at a solution for a complete problem. It is then said, it must be "the best local choice among all feasible choices available on that step".

Since both involve local optimality, isn't one a subset of the other?

Answer 1

The difference is that dynamic programming requires you to remember the answer for the smaller states, while a greedy algorithm is local in the sense that all the information needed is in the current state. Of course, there is some intersection.