贪心用法总结

贪心用法总结

1、技巧展示

说到贪心问题，首先想到背包客问题，问怎么装东西才能使得背包所装物品的价值最大，那么我们就首先调选价值大的物品装进背包，然后依次将剩下的物品装入到背包中。在写过贪心问题的题解之后，在这里做一个总结。

目的：使用贪心的目的，就是为了能够能快地解决问题(个人理解)。比如，要求最大，那么我们在每次选择上都选最大。要求最长，那么我们在每次选择上都选最长。要求最短时间，那么我们在每次选择上都选择最短时间。(小tips：贪心并不一定能够得到全局最优解)

技巧：

①贪心思想求最大问题

解释：使用贪心思想求解最大值问题时，我们在求解过程的每一步都坚持选大不选小的原则，然后即可得到问题的答案。

②贪心思想求最小问题

解释：在使用贪心思想求解最小值问题的时候，我们在求解过程的每一步坚持选小不选大的原则，同样得到问题的答案。

2、小试牛刀

题目①通配符匹配

本题使用了技巧①，在对'*'号通配符匹配的时候，我们尽量选择最大值进行匹配。

题目②连续子数组的最大和

本题使用了技巧①，在求解子数组的最大和时，只要子数组再加上当前值大于0，我们就认为该子数组的值有很大可能会增加，因此进行记录，并最终返回答案。

题目③分糖果问题

本题使用了技巧②，对于分配的最少糖果，我们用贪心思想，如果一个孩子的分数大于另一个孩子的分数，我们只给1颗糖，这样每一次求解都是在追求最小值，最后便得到最少的糖果数。

题目④买卖股票的最好时机(二)

本题使用了技巧①，在求解本题时，只要相邻两个数呈增长趋势，就记录，即每一步都记录最大值，最后返回卖股票多能盈利的最大钱数。

题目⑤主持人调度

本题使用了技巧②，将活动时间排序，按照主持人能主持就全力主持的原则，每一次都坚持最小主持人数，最后便得到最少主持人数。