greedy vs dynamic [closed]

It's difficult to tell what开发者_StackOverflow社区 is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

I have some general question about algorithms, when You have some problem and You want to write some algorithm, how do You approach the problem, how do You decide which algorithm to use greedy one or dynamic programming? thanks in advance

---

In general I try to transform the new problem into a well known problem that has a well known solution. Then selecting the right algorithm is trivial. This covers most cases in the wild in my experience.

If step one fails I try a greedy approach and try to prove that it doesn't work. The proving part can be tricky but basically you have to show that the local best choice in some intermediate step isn't going to yield an overall best result. From there I branch out and usually dynamic is one of the first alternatives I try.

If all else fails, I start looking at good approximation algorithms which are close enough for the problem at hand. Many problems can be solved "well enough" with approximation in a fraction of the time and resources making it the clear winner.

---

If a greedy algorithm would work I will prefer that, if not, then if dynamic programming works then choose that one, otherwise something with worse asymptotic behaviour.

How could you seriously expect to get an answer for your question?

All dynamic programming tasks have a feature that an optimal solution for a (well chosen) sub-problem is also part of the optimal solution for the whole problem. You either discover this feature of the problem in question or you don't...

Update: I would like to tell you the nice answer that "I map it to a similar well known problem" but that's not what I do. I solved a couple of DP problems and since then if I see something that will yield O(2^n) with a brute force algorithm, I automatically start to search for sub-problems from which the optimal solution can be constructed.