Greedy algorithm/ dynamic programming


#1

define the control abstraction of dynamic programming and how it differs from Greedy paradigm.?


#2

In Dynamic programming, we first find solution of a sub problem an then from that sub problem solution and relation between that sub problem and original problem we find solution of original problem. It is somewhat similar to recursion but difference between recursion and dp is - in dp we act quite smartly and store result of the sub problem in order to calculate result of the original problem.

  Greedy is a paradigm in which we choose the one which seems best at the moment. But after some steps we might realize it was not an optimum choice. In dp, we choose result which is best in future as well. It doesn't mean greedy always gives wrong answer, but we have to prove that it indeed gives the optimal answer.

   You can see the link if you want to look more - https://stackoverflow.com/questions/16690249/difference-between-dynamic-programming-and-greedy-approach