Abstract
Quote
- 向日葵朝着太阳转动， 时刻都在寻求当前汲取最大养分的可能。
- 最优子结构就是追随太阳最高效的移动轨迹。
- 移除重复子问题让向日葵紧跟太阳的脚步。
- 贪心策略在一轮轮的简单选择中，逐步导向最佳的答案。
- Solves problems around Combinatorial Optimisation
- Usually better performance than Backtracking & Dynamic Programming
- Think about what is the Local Optimal Solution. If it feels with the current stage optimal solution can form the global optimal solution, can give a try of the greedy approach
- Follow pre-defined procedures for each stage
Comparison with Dynamic Programming
Both rely on Optimal Substructure (最优子结构).
Differences
- Greedy algorithms find a locally optimal solution at each step and never goes back to reconsider its choice. This means greedy algorithm may find a solution that is actually not the most optimal choice! Dynamic Programming is determined to find global optimal by exhaustively search through all of the possible subproblems, and then choose the best solution based on that.
- Greedy algorithms often simpler and more efficient than dynamic programming.
When greedy shines?
Guaranteed to get the Global Optimal Solution
When we can’t find an counter-example with the greedy approach.
Sub-optimal solution is good enough
When finding Global Optimal Solution takes too much effort & a Sub-optimal solution gets the job done.
Tips to Solve Greedy Problems
Greedy at different stages
- We can use Greedy Loop more than once in a problem
- For example, for question 1005, we use the first Greedy Loop to ensure all possible negative numbers are negated to positive numbers. Then, we can use the second Greedy Loop to negate the smallest positive integer when there is still negation left to use
- The first Greedy Loop ensures we get the maximum value from negating the negative values in the array. The second Greedy Loop ensure we lose the least from negating array with all positive values
Obtain Optimal Substructure
- One way to obtain Optimal Substructure is by sorting the given input
- Basically limit the impact range of each element to its adjacent neighbours
Questions
Basics
- For some questions, we can apply greedy loop more than once, for example the problem 1005 below
Leetcode
CodeForces
Sub-Sequence
- The order of the elements cant be altered, refer to Sub-Sequence
Leetcode
Array
Leetcode
CodeForces
Stock Problems (股票买卖问题)
Greedy By Parts (2-Dimensions)
- 135. Candy, we can be greedy to ensure proper distribution of candies on the left side, then greedy again to ensure proper distribution of candies on the right side. Then with both left and right, we are able to fulfil the requirement of Children with a higher rating get more candies than their 2 neighbors
Leetcode
CodeForces
Interval Problems (区间调度问题)
-
The trick is to think about finding the maximum range/reach
-
Use the smallest steps to increase the most amount of range/reach. We get the answer once the range/reach arrives at the last index of the given array
-
55. Jump Game only has 1 range/reach to keep track of
-
45. Jump Game II has 2 range/reach to keep track of, one is the maximum reach/range of current step, another one is the maximum reach/range of next step
-
452,435, 56, we rely on sorting to make each entity next to each other, to form the Optimal Sub-structure to perform greedy algorithms
Leetcode
CodeForces
Recursion
Leetcode
Terminologies
Greedy Loop
- Looping through a collection, and apply a greedy algorithm on the elements