title: How is dynamic programming different from greedy algorithms?
body: <p>In the book I am using <a href="https://rads.stackoverflow.com/amzn/click/com/0201743957" rel="noreferrer" rel="nofollow noreferrer">Introduction to the Design &amp; Analysis of Algorithms</a>, <em>dynamic programming</em> is said to focus on the <strong>Principle of Optimality</strong>, "An optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances".</p>
  
  <p>Whereas, the <em>greedy technique</em> 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".</p>
  
  <p>Since both involve local optimality, isn't one a subset of the other?</p>