It so happens that apart from being an active member on Code forces I spend quite some time on stackoverflow.com trying to provide help for users around the world. Every now and then I see a question where the most upvoted and accepted answer is not entirely correct but this time it is a bit different. Take a look at this question: http://stackoverflow.com/q/13713572/812912 The discussion is pretty much on what is greedy and DP and isn't one of them a subset of the other. The most upvoted and accepted answer states the following:
The difference between dynamic programming and greedy algorithms is that with dynamic programming, the subproblems overlap.
(take a look at the whole answer here)
In fact the whole answer is quite interesting. I tried to start a discussion with the poster, explaining what is wrong but I keep getting more and more interesting statements. Here is an example(in the comments section):
@IvayloStrandjev: No, Dijkstra's without the heap would be a greedy algorithm. The heap introduces a dependency whereby when a decision is made about a solution to a subproblem (the shortest path to a vertex) is used to facilitate the decisions to the other subproblems. This is why Dijkstra's is not simply a greedy algorithm (or else you would have to make the decisions independently). This agrees with the top Quora answer. – Neil G Sep 18 at 13:54
If you also read through the chat you will notice that the same user claims that computing the n-th Fibonacci number using memoization is DP(which is correct), but without memoization it would be greedy(which is nonsense).
It is first time I see an accepted answer that is so off target and where the poster ignores any reasoning. Truth is that this case annoys me quite a lot — I see something that is totally incorrect and yet it seems to be accepted by the community. More people would read this answer and most will believe it is correct. Thus I am turning to code forces community for some support. Apparently my opinion is not authoritative enough and the links I provide are not enough. I would also like to hear what you think on the whole discussion.
It makes no sense to argue whether Dijkstra's algorithm is or isn't "greedy". There is no formal definition of what is and what isn't a "greedy algorithm".
The word "greedy" is an informal way of describing an observation during problem solving / algorithm design: we use "being greedy" as shorthand for "making the locally optimal choices". Hence, when we say "the problem can be solved greedily", we mean "the sequence of locally optimal choices will actually bring you to the globally optimal solution".
As for Dijkstra: Is there a greedy aspect to the algorithm? Certainly yes. You always select the currently best unprocessed vertex to be processed next. Should the algorithm be classified as a "greedy algorithm"? Probably not, such classification would be misleading. This is because the greedy choices are not everything the algorithm does. Processing a new vertex does actually change the state of the algorithm and influence the future choices it will be making. The algorithm has to store and re-use information in a clever way, in addition to the greedy choices it makes.
Similarly, there is a dynamic programming aspect to Dijkstra's algorithm, but I believe it is misleading to label it as a pure "dynamic programming algorithm": it's not just a single recursive relation where each subproblem only references other, strictly smaller subproblems.
Most of the arguments about such topics arise because people care too much about names and categorization, and they care too little about the actual ideas.
I agree with what you say(not that I could ever disagree with you). The reason I am starting this discussion is because I believe the accepted post is absolutely misleading. It adds nothing to explain what is greedy and instead it defines it as an opposition to DP, which is wrong. I am afraid that future readers will be mislead by this post and the fact that it is accepted.
Obligatory XKCD link: xkcd: Duty Calls
It's quite likely that you are correct, but I feel the battle you chose is similar to Don Quijote's battle with the windmills. Maybe there are better places to spend your energy.
Don't worry too much about future learners. Nobody is forcing them to accept any answer at face value, they also get to think about them and decide whether they agree. There is a long way from asking the question "What is the difference between greedy and DP?" to understanding that the question is meaningless. And maybe it's actually good to read many different, disagreeing opinions at some point during that journey.