最优子结构：规模较大的问题的解由规模较小的子问题的解组成，
最有名的的贪心思想就是Dijstra算法了。
note：贪心是一种聪明的搜索，但这种聪明是以严谨的数学证明作为代价的，这些是数学家干的活（例如拟阵等），普通人只需用结论即可。
无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
贪心选择性质：从局部最优解可以得到全局最优解，这个也是思考的难点。
怎么就知道局部最优了，全局就是最优了呢？
一般使用推导和举反例来证明；
如果举不出反例，就可以使用贪心算法；
贪心的解题步骤：
- 将问题分为若干子问题；每做一个贪心选择就将大问题简化成规模小一点的子问题；
- 找到合适的贪心策略；
（设计数据找规律，进行贪心猜想，例如：每次都选择最大/最小/前n个/最多/最少等等）； - 根据第二点选择的贪心策略，求解每个子问题的最优解；
- 将每个局部最优解，叠加起来就成了全局最优解；
贪心作为一种算法策略，很多情况下需要借助优先队列来实现（优先选择前n个，n>=2）。
根据贪心策略，对要处理的数据先排序，排序之后的数据就是贪心选择策略。
455.分发饼干 https://leetcode.cn/problems/assign-cookies/
将饼干排序，将小孩胃口值排序；每次用最小的饼干满足当前胃口最小的小孩;
-
柠檬水找零 https://leetcode.cn/problems/lemonade-change/
收到20元的时候，优先找10 + 5；如果10 + 5不存在，才选择5+5+5；尽量保留多的5美元； -
无重叠区间 https://leetcode.cn/problems/non-overlapping-intervals/
找不重叠的最大区间个数；
1. 将区间按照右边界从小到大排序；
2. 遍历整个区间，寻找不重叠，而且右边界尽量小的区间；
3. 如果能找到不重叠的子区间，进入下一轮寻找；找不到跳出循环； -
最长回文串 https://leetcode.cn/problems/longest-palindrome/
将每个字母出现次数按照从高到低排列；
每次优先选择最多次数的字母(偶数个取偶数个，奇数个减去1)； -
验证回文字符串 Ⅱ https://leetcode.cn/problems/valid-palindrome-ii/
左右指针只要出现不一致，就贪心选择要删除一个字符；然后判断剩余字符是否是回文字符； -
课程表 III https://leetcode.cn/problems/course-schedule-iii/
每次选择课程的时候，都贪心地选择课程最早结束的课程；课程结束晚后面还有机会选择； -
最多可以参加的会议数目
https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/
如果当天有n个会议要参加，贪心地选择最早结束的会议；因为晚一点的会议后面还有机会选择； -
最低加油次数 https://leetcode.cn/problems/minimum-number-of-refueling-stops/
1. 将问题分为若干子问题；
每到下一个加油站，需要加油的次数；记为：count(i);
2. 找到合适的贪心策略；
2.1 如果当前油能支持到下一个加油站，不加油；
2.2 如果当前油不能支持到下一个加油站，则从备份的经过的加油站里面按照从大从小的顺序寻找加油站，直到首次满足到达下一个加油站的最小油量；
3. 根据第二点选择的贪心策略，求解每个子问题的最优解；
每到一个加油站，都按照上面的策略计算count(i);
4. 将每个局部最优解，叠加起来就成了全局最优解；
将所有的count求和；
- 最长数对链 https://leetcode.cn/problems/maximum-length-of-pair-chain/
将数对按照第二个数的升序进行排序，每次贪心选择数对中第二个数最小的，这样整体解才会达到最大；
最著名的贪心思想莫过于单源最短路径算法。
