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.
