贪心算法就是一种直觉上更优的策略
交换论证法
本质
通过把假设的最优策略的前后选择交换，如果可以证明：在任何情况下，最优策略可以不失去最优性而转化成贪心策略，说明贪心策略就是最优的一种表现形式
例题
- 理解题意可以发现，假设我们身上同时好多种钞票，那么根据我们找钱的方案不同，结果也将不同，因此第一时间想到了多叉树暴搜，但遗憾的是会超时。
- 因此考虑贪心算法，即每次都选最有利于后续找钱的方案，这也不难想到，留着两个5肯定比留着一个10更有用，因为5还可以找10，而10只能找20。
- 我们得出一种贪心方案：假设此时要找20元，并且手里至少有3个5元和1个10元，我们选择找一个5元和一个10元而不是3个5元（需要做出选择的就这一种情况）。
证明：
- 首先这道题的方案太多了，比较难入手，其次，直觉上来讲，每次都挑最大的减半一定是最优策略。
- 因此我们得出一种贪心方案：每次都找当前数组中最大的数进行减半。
证明：
- 首先这道题先想到的肯定是动态规划，而这道题有两种动态规划的思路：第一种是层次划分，第二种是组合划分，层次型划分比较难想，组合划分好想但是效率低（n^2）
- 而根据对结果的观察，我们可以的出一种贪心策略，每次都选择波峰或者波谷，在逻辑上，每次选最边界的值可以让下一次有更多种选值方式
证明：
补充一下动态规划层次型划分的解析：
- 从贪心的角度思考，因为我们要求更多的胜场数而不是更多的分数，因此nums1只要捡nums2中的软柿子捏即可，因此对nums2排序，依次给nums2中的元素匹配对应的nums1中的元素。而对于nums1来说，他要尽可能的保留大数，使用小数，这样可以尽可能匹配更多，因此nums1也排序，优先使用小数。在匹配过程中如果nums1的元素小于等于了nums2的元素，说明nums1中的该元素无论如何也无法胜利，但他一定会上场，因此让它比拼nums中最大的元素，这样nums1可以欺负弱小的，废物利用最大化。
证明：
编写方法：
这道题也是优势洗牌类型，参考证明如下：
每次要减数字的时候，都有两种选择：减X或者减2X。当然我们希望减去2X。所以问题其实分两层，第一，能不能减2X，第二，现在减2X是不是最优。
对于第一个问题，我们只需要判断剩余大小N%2X是否为0，为0就是可以减。因为后续有可能减去2X、4X、8X... ...这些无一例外都是2X的倍数，所以如果N不是2X的倍数，那现在选了2X就一定不会恰好减到0。
对于第二个问题，其实能选则选是最好的。如果此次不选2X，后续只可能选偶数个X，如果不选偶数个那么N不可能是2X的倍数，会导致无法减0，当然你也可以一直选X，这明显差于贪心策略。反之，如果后续选了偶数个X，那为什么不把偶数个X变成若干个2X呢？
综上贪心策略得证
反证法
本质
假设贪心策略不正确，然后推翻假设。
例题
- 我们第一时间想到的是，假设两个数要拼起来的话，那肯定是谁的最高位上的数字最大把谁放前面最好，如果最高位相同，那么就比较下一位谁大，以此类推。由于数组中的元素的位数是不确定的那么比较逻辑要考虑的情况就较多，时间复杂度也较高。
- 因此实际上我们可以直接把两个数按照两种组合方式组合一下（转字符后），然后比较一下，这样还比较方便。
- 对于多个数来说，我们假设这样一种贪心策略：定义一种排序规则，如果ab>ba那么说明a应该放在b前面，按照这种规则排序就能得出最终答案。
证明：
当然还得证明这种规则真的能排序（利用全序关系），过程较复杂
- 该题无非是想让我们求如何买卖（不限次数）可以让利润最高，而利润的大小可以用折线图总的上升区表示，因此我们定义一种贪心策略：将价格折线图中的所有上升区相加即是最大利润。
证明：
递进证明法
本质
这类型题的贪心策略比较明显，采用递进证明法，即前一个选择可以推出后一个一定成立，依此类推。
例题
贪心策略+证明：
- 遇到‘I’就选择当前集合中最小的元素，这样保证后面无论选什么都是上升的；遇到D就选择当前集合中最大的元素，这样无论后面选什么都是递减的。
- 首先要想到问题转换，把该问题当作在n个空格上放置元素使相邻元素不相等，否则没有入手点。
- 贪心策略为：首先把个数最多的一种元素间隔为1放上去，然后依次放剩下的元素。
- 证明：
首先第一种元素（元素数量最多的元素）的个数绝对不会超过奇数位的个数，因为一旦超过了，不论如何放置（我们已经尽量让同种元素之间的间隔最小以容纳更多元素了），那一定会出现相同元素相邻。所以第一种元素一定能正确放置。
接下来的多种元素的放置有两种情况，第一种就是该种元素都放置在偶数位或者奇数位，可以预见，不会出现问题。
第二种就是一部分放在奇数位，一部分放在偶数位，可以预见，假设该种元素的个数超过了第一种元素的个数才会出现问题，但我们已经把数量最大的元素先放置了，所以该元素的数量肯定没有第一种元素多，这种情况不会发生。
直观正确
本质
这类型题的贪心策略非常明显，无需证明。
例题
贪心策略如下：
贪心策略如下：
- 回文串的组成就是同一类型的两个字母分列字符串两侧，所以我们只需要数量为2的字母即可，最后如果还剩下字母就放在回文串中间，也就是长度+1。
贪心策略如下：
- 除法可以转换成分子分母的形式，因此求除数最大就是求分数最大，也就是尽可能让分子变大，分母变小。
- 经过观察可以发现，数组中的第一个元素始终都在分子上，而数组中的第二个数始终在分母上，无论如何改变优先级。a/(b/c/d/e/f)可以让剩下的数都放在分子上，因此这种策略得出的结果最大
- 贪心策略：只要两个区间有重叠就一定要有一个区间被移除，而我们要去除的就是有边界更大的区间。
- 证明：
贪心策略：
- 首先桶为0，蓄水池不为0，那么必定要进行一次扩桶操作，所以可以按照这个对其预处理一下，计算至少需要扩桶几次并把对应的桶扩充。
- 接下来就是选择一种策略让操作次数最少了，总共只有两种操作：扩桶，蓄水，我们所求的策略不过是这两种操作分别做多少次罢了。因此我们可以枚举蓄水的次数，蓄水次数最大也就是max(vat[0]/bucket[0],vat[1]/bucket[1],...)，此时扩桶次数为0。如果蓄水次数再大就没有意义了。
- 每次枚举蓄水次数的时候，都可以通过计算每个池子以该次数蓄水蓄满最少需要的桶的容量与当前桶的容量之差来计算本桶的最少扩桶次数，所有桶的次数叠加就是总的扩桶次数。最终取扩桶+蓄水总次数最大的即可
