贪心算法，是在对问题求解时，总是做出在当前看来是最好的选择，即只考虑某种意义上的局部最优解。
对于某种意义的思考，应该是考虑无后忧性，即局部最优不影响整体最优。贪心算法一般都需要证明我们找到的解就是答案要求的最优解，证明方法通常是替换法。
即假设存在某个最优解，证明我们用贪心算法找到的解和这个最优解是一样的或者效果一样。

（ps:大概过一周更新贪婪算法的应用）

如：leetcode #45跳跃游戏ii,#55跳跃游戏，#135分发糖果

（1）#45跳跃游戏ii
1>题目：
给定一个非负整数数组，你最初位于数组的第一个位置。

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

2>思路：

考虑局部最优，我从第一步开始跳跃，最远可以跳a[0]步，那么在a[1]到a[a[0]]这些数组元素里循环，如果能找到某个元素a[i]，
这个a[i]相比其他元素跳的更远或者一样远，这就是我们要找到的局部最优，因为其他元素能够跳到的地方，a[i]也能够到达。

证明：假设答案要求的最少步数是k步，对应序列为a[i0],a[i1],...,a[ik],我们用贪心算法找到的最优解序列是a[j0],a[j1],...,a[jk],a[j(k+1)],...
a[i0]=a[j0],根据我们前面讲的思路，利用贪心算法得到的a[j1]...，一定有a[j1]>a[i1],a[j2]>a[i2],...
(因为我们的a[j]序列是当前元素代表的步数相比其他位置元素能到达更远地方的,比如思路里的a[0],a[i],...这样往下写)
因此，a[jk]>a[ik],既然a[ik]能一次到达末尾，那么a[jk]也一定可以，因此用贪心算法找到的也是最优解。

3>参考代码:

class Solution {
public:
    int jump(vector<int>& nums) {
        int ret = 0;
        int steps = nums[0];
        int i = 0;
        int pos = 0;
        int a = 0;
        int lenth = nums.size();
        if (lenth == 1)
            return 0;
        while (nums[pos] < lenth - pos - 1)
        {
            int tmp = 0;
            steps = nums[pos];
            for (i = 1; i <= steps; ++i)
            {
                if (steps + nums[a + i] + i > tmp)
                {
                    tmp = steps + nums[a + i] + i;
                    pos = a + i;
                }
            }
            ++ret;
            a = pos;
        }
        ret += 1;
        return ret;
    }
};

(2)#55跳跃游戏

1>题目:
给定一个非负整数数组，你最初位于数组的第一个位置。

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

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

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

2>思路:

可以和跳跃游戏ii的做法一样，用一样的方法，如果我在循环的过程中，停在了数组元素为0的位置，说明肯定跳不到终点，
反之则可以达到终点，其中注意对边界讨论，比如只有一个元素，且这个元素就是0，这也是算作可以到终点的。

3>参考代码:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int steps = nums[0];
        int i = 0;
        int pos = 0;
        int a = 0;
        int lenth = nums.size();
        if (lenth == 1)
            return true;
        if (nums[0] == 0)
            return false;
        while (nums[pos] < lenth - pos - 1)
        {
            int tmp = 0;
            steps = nums[pos];
            for (i = 1; i <= steps; ++i)
            {
                if (steps + nums[a + i] + i > tmp)
                {
                    tmp = steps + nums[a + i] + i;
                    pos = a + i;
                }
            }
            if (nums[pos] == 0)
                return false;
            a = pos;
        }
        return true;
    }
};

4>另一种思路（另一种意义下的局部最优解）

我们可以逆向遍历数组，从数组末尾开始，判断前一个位置a是否能到达"当前位置"b（开始时当前位置就是末位置），如果可以，更新"当前位置"为a,
再判断新的前一个位置能否到达"当前位置"，如果0(数组第一个元素)也被更新成了"当前位置,说明可以到终点，反之则不可以。

参考代码：

class Solution {
public:
    bool canJump(vector<int>& nums) {
    
        int i = 0,lenth=nums.size();
        int pos = lenth-1;
        for (i = lenth - 1; i >= 0; --i)
        {
            if (i + nums[i] >= pos)
                pos = i;
        }
        return pos == 0;
    }
};

(3)#135分发糖果
1>题目:
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

2>思路:

这里的局部最优，就是把当前位置的元素与两端的元素做比较，如果大于，则要保证分配相应多的糖果。
但是不能直接在一个循环里面进行两次比较，比如位置1,2,3,4，分数：1<2,2>3>4,如果一次进行两次比较的话，
第一次：假设位置1分配的糖果为1，则位置2分配糖果数2，位置3分配1.
第二次：由于位置4分配糖果1，所以位置3分配糖果至少是2，与位置2分配的糖果相等。
出现问题的根本原因是当我在和下一个位置进行比较的时候，下一个位置糖果数目还没有更新，必须等到下一个位置糖果数目更新后才能比较
（即应该先让下一个位置和下下个位置进行比较，这个任务由逆向循环完成）
因此，可以考虑把两次比较分开进行，用两次循环，第一次从左往右，第二次从右往左，这样就不会有上述问题了。

3>参考代码：

class Solution {
public:
    int candy(vector<int>& ratings) {
    int lenth = ratings.size();
        vector<int>ret(lenth,1);
        int i = 0;
        for (i = 1; i < lenth; ++i)
        {
            if (ratings[i] > ratings[i - 1]&&ret[i]<=ret[i-1])
            {
                ret[i] = ret[i - 1] + 1;
            }
        }
        for (i = lenth - 2; i >= 0; --i)
        {
            if (ratings[i] > ratings[i + 1]&&ret[i]<=ret[i+1])
            {
                ret[i] = ret[i + 1] + 1;
            }
        }
        return accumulate(ret.begin(), ret.end(), 0);
    }
};

（这个方法来自于博客：https://blog.csdn.net/qq_21567767/article/details/81987689）