Greedy Algorithm
Definition
Making the optimal choice at each stage with the hope finding the global optimum.
Pros: Easy to implement, fast
Cons: Very often don't provide a globally optimum solution
Example of situation when greedy algorithm don't work
For example in here we want to find the Binary Tree Maximum Path Sum.
Following a greedy algorithm will lead to the wrong answer as 3,7,11 whereas the actual answer is 3, 4, 20
When to use
We need 2 properties
- Greedy choice: a global optimum can be arrived by selecting a local optimum
- Optimal Structure: an optimal solution of the problem contains optimal solution to subproblems.
Greedy vs Dynamic programming
Greedy never reconsider its selection, whereas dynamic programming will exausted and guaranteed to find the solution.