# Dynamic programming VS Greedy Algroithms [closed]

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?

-

## closed as unclear what you're asking by D.W., David Richerby, Juho, vonbrand, Wandering LogicApr 14 '14 at 17:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

Does the course have any particular formal definition of "greedy algorithm" and "dynamic programming" in mind? –  Yuval Filmus Apr 7 '14 at 1:50
What are your thoughts? What effort have you made on your own? What aspects of the question have you confused or uncertain about how to answer? Are there any aspects of dynamic programming and/or greedy programming that you are fuzzy about? –  D.W. Apr 7 '14 at 6:53

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.

-
Along the same lines I have the question True or False Dynamic programming requires that the optimization problem has a recursive solution? any input there? –  Deekor Apr 7 '14 at 3:31
What do you mean by recursive solution? Referring to this other post on stackoverflow stackoverflow.com/questions/2093618/… you can reason that you will always be able to have an iterative solution in its place, unless you meant something slightly different. –  Francesco Gramano Apr 7 '14 at 3:46
not really sure what he means, my professor wrote the question. –  Deekor Apr 7 '14 at 3:55
Well, if a problem requires dynamic programming then its solution would be inductive in that you would have to solve the problem in terms of its subproblems; however, you would be able to express it iteratively, so recursion isn't required per se. –  Francesco Gramano Apr 7 '14 at 3:59