[Solved]: Dynamic programming VS Greedy Algroithms

Problem Detail: 

I have two True or False questions in my practice test that are related but I am unsure about:

1. If an optimization problem can be solved using a greedy algorithm,  there must be a solution for this optimization problem using dynamic programming as well.  2. If an optimization problem can be solved using dynamic programming,  there must be a solution for this problem using a greedy algorithm as well. 

I think the answers are 1. True and 2. False is this correct?

Asked By : Deekor

Answered By : Francesco Gramano

Sounds about right, however informal the statement; dynamic programming is more powerful than greedy algorithms so if a problem should require it, a greedy algorithm won't be enough. And in the case in which a greedy algorithm can solve the problem, there will also be a correct dynamic programming solution since dynamic programming involves solving problems by optimizing overlapping subproblems. Suppose a greedy algorithm suffices, then the local optimal decision at each stage leads to the optimal solution and you can construct a dynamic programming solution to find the optimal solution. However, greedy algorithms are generally faster so if a problem can be solved with a greedy algorithm, it will typically be better to use.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23493