What is the differences between dynamic programming and greedy approach?
Greedy vs. Dynamic Programming :
Both techniques are optimization techniques, and both build solutions from a collection of choices of individual elements
- The greedy method computes its solution by making its choices in a serial forward fashion, never looking back or revising previous choices.Dynamic programming computes its solution bottom up by synthesizing them from smaller sub solutions, and by trying many possibilities and choices before it arrives at the optimal set of choices.
- There is no a priori litmus test by which one can tell if the Greedy method will lead to an optimal solution . By contrast, there is a litmus test for Dynamic Programming, called The Principle of Optimality
You can also refer to this answer on stack overflow → link text
1 Like
DP VS Greedy
- A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage
- A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states
- Greedy Algorithm works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later
- DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc.
1 Like