一、概念
百度百科的解释：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

所以贪心算法也存在如下问题：

1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑；

2、贪心算法一般用来解决求最大或最小解；

3、贪心算法只能确定某些问题的可行性范围。

二、贪心算法的基本要素
贪心算法通过一系列选择来得到问题的解，所做的每个选择都是当前状态下局部最好选择，即贪心选择。许多可以用贪心算法求解的问题中可以看到，它们一般具有两个重要的性质：

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才可以做出选择；而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。再去解做出这个选择后产生的相应的子问题。

贪心算法所做的贪心选择可以依赖以往所做过的选择，但决不依赖将来所做的选择，也不依赖子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

2、最优子结构性质（和动态规划中的概念一致）

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

三、贪心算法与动态挂规划的区别
当一个问题具有最优子结构性质时，可用动态规划法求解。有时会有更简单有效的算法。

考察找硬币的例子。假设有4种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给顾客六角三分钱。这时，自然地拿出2个二角五分的硬币、1个一角的硬币和3个一分的硬币交给顾客。这种找硬币方法与其他找法相比，拿出的硬币个数是最少的。这里使用的找硬币算法为：首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去三角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这个方法实际上就是贪心算法。 顾名思义，贪心算法总是做出在当前看来是最好的选择。 也就是说，贪心算法并不从整体最优加以考虑，所做的选择只是在某种意义上的最优选择。当然，我们希望贪心算法得到的最终结果也是整体最优的。找硬币算法得到的结果就是一个整体最优解。

找硬币问题本身具有最优子结构性质，可以用动态规划算法来解，但贪心算法更简单，更直接，并且解题效率更高。这利用了问题本身的一些特性。例如，上述找硬币的算法利用了硬币面值的特殊性。如果硬币面值改为一分、五分和一角一分，而要找给顾客的是一角五分钱。还用贪心算法，将给顾客1个一角一分的硬币和4个一分的硬币。然而3个五分的硬币显然是最好的找法。虽然贪心算法不是对所有问题都可以得到整体最优解，但是对范围相当广的许多问题能够产生整体最优解，如最小生成树问题、图的单源最短路径问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。

贪心算法和动态规划算法的差异：

共同点： 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是这两类算法的一个共同点。
区别： 动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题时才能做出选择。而贪心算法，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。
贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；

动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解 。

举例说明：也就是说，假如你要求第十步的最优解，那么第十步的最优解肯定与第九步的最优解有关，而第九步的最优解肯定与第八步的最优解有关。可以这么理解，贪心算法第十步的最优解得把前面九步的最优解都用上了，但是动态规划你需要求第十步的最优解，这个最优解可能只与第八步，第三步，第一步有关，与第九步没有关系，我们为什么选择第八步而不选择第九步呢？是因为我们在计算第十步的最优解的时候其实把1-9步的组合的情况都计算了，选择了其中最优的解，也就是第八步的解，其实第十步解的构成与第九步没有关系，动态规划相当于穷举了1-9步最优情况下的组合，选了其中最优的作为第十步的最优解，而贪心算法第十步的最优解肯定是由第九步构成的。

求一个问题的最优解相当于遍历所有的子集来找最优解，但是这样解随着解空间的维度成指数增长，动态规划其实就是一种遍历，但是他是带备忘录的遍历，对于前面算到的子问题，仅就不在计算而是直接查看备忘录，直接调用之前保存的值，这样就节省了大量的时间。

四、贪心算法思路
贪心算法一般按如下步骤进行：

①建立数学模型来描述问题。

②把求解的问题分成若干个子问题。

③对每个子问题求解，得到子问题的局部最优解。

④把子问题的解局部最优解合成原来解问题的一个解。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。

五、例子
55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
1
2
3
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
1
2
3
我们可以用贪心的方法解决这个问题。

设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 y，即 x+nums[x]≥yx，那么位置 y也可以到达。

换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯ ,x+nums[x]这些连续的位置都可以到达。

这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。

在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

以题目中的示例一 [2, 3, 1, 1, 4] 为例：

我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；

我们遍历到位置 1，由于 1≤2，因此位置 1可达。我们用 1加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。

我们再来看看题目中的示例二 [3, 2, 1, 0, 4]
我们一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；

我们遍历到位置 1，由于 1≤3，因此位置 1 可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；

位置 2、位置 3 同理，最远可以到达的位置不会被更新；

我们遍历到位置 4，由于 4>3，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。

在遍历完成之后，位置 4 仍然不可达，因此我们返回 False。

class Solution {
    // 贪心
    public boolean canJump(int[] nums) {
       int maxRightIndex = 0;
       for (int i = 0; i < nums.length; i++) {
           // i <= maxRightIndex 说明可以到达位置i
           if (i <= maxRightIndex) {
               maxRightIndex = Math.max(maxRightIndex, i + nums[i]);
               if(maxRightIndex >= nums.length - 1) {
                   return true;
               }
           }
       }
       return false;
    }
}
————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
                        
原文链接：https://blog.csdn.net/wang_luwei/article/details/130307642