贪心算法总结

还是通过一道题来总结

跳跃问题

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

贪心算法解题分析：

这道算法题作为引入，主要体现了贪心算法的最直接的特点——“贪婪”，每一步都选择都选择从当前所在位置出发可以到达的最远距离，如给出一组数据list=[2,3,1,1,4]，对于位置0，list[0]=2,即使可以选择跳0,1,2步，但是我们“贪心的”只关注最远的mostlong的值，遍历整个数组，循环用mostlong=max(mostlong,i+nums[i]);更新mostlong的值，直到找到可以达到的最右端的位置。

代码实现：

class Solution

 { 

public:

 bool canJump(vector& nums)

 { 

int mostlong=0; 

for(int i=0;i

 {

 mostlong=max(mostlong,i+nums[i]); //贪心选择右端可达最大值 

if(mostlong

return false; 

} return true;

 } 

};

看了这么多博客后，我觉得贪心法做出的选择就是对于当前所处状态的最优选择，它的解决问题的视角是微观的“局部”，而不是从全局宏观的角度思考和看待问题，根据这样的性质，要求贪心法解决的问题有“无后效性”——当前的决策不会影响到后续的决策，因为如果问题前后勾连紧密的话，会造成求解过程十分混乱。贪心算法常常用于组合优化问题，它的求解过程是多步判断的过程。

总结来说，如果一个待求解的问题具有以上的特征，很有可能可以使用贪心算法解决。

如果想要证明某一贪心策略不正确，可以寻找反例（如“活动安排问题”的开始时间最早、持续时间最长这两种贪心策略都是通过举反例的方法排除的）。