贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。
比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。
什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一小部分问题拥有这个性质。比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。
然而，大部分问题都明显不具有贪心选择性质。比如打斗地主，对手出对儿三，按照贪心策略，你应该出尽可能小的牌刚好压制住对方，但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法，而得使用动态规划解决。
实例1：区间调度问题：
给你很多形如[start,end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。
int intervalScheduling(int[][] ints) {}
举个例子，intvs=[[1,3],[2,4],[3,6]]，这些区间最多有两个区间互不相交，即[[1,3],[3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间[start,end]表示开始和结束的时间，请问你今天最多能参加几个活动呢？
错误思路：这个问题有许多看起来不错的解决思路，实际上都不能得到正确答案。比如说：也许我们可以每次选择可选区间中开始最早的那个？但是可能存在某些区间开始很早，但是很长，使得我们错误地错过了一些短的区间。或者我们每次选择可选区间中最短的那个？或者选择出现冲突最少的那个区间？这些方案都能很容易举出反例，不是正确的方案。
正确的思路其实很简单，可以分为以下三步：
- 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
- 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
- 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
把这个思路实现成算法的话，可以按每个区间的end数值升序排序，因为这样处理之后实现步骤 1 和步骤 2 都方便很多:
由于我们预先按照end排了序，所以选择 x 是很容易的。关键在于，如何去除与 x 相交的区间，选择下一轮循环的 x 呢？由于我们事先排了序，不难发现所有与 x 相交的区间必然会与 x 的end相交；如果一个区间不想与 x 的end相交，它的start必须要大于（或等于）x 的end：（画一个简单的坐标图就可以知道）in
public int intervalScheduale(int[][] intvs){
if(intvs.length ==0){
return 0;
}
Arrays.sort(intvs,new Comaparator<int[]>(){
public int compare(int[] a, int[] b){
return a[1] - b[1];
}
});
//至少有一个区间不相交
int count=1;
//排序后，第一个区间就是x
int x_end=intvs[0][1];
for(int[] interval : intvs){
int start=interval[0];
if(start>=x_end){
//更新x
count++;
x_end=interval[1];
}
}
return count;
}
对于区间问题的处理，一般来说第一步都是排序，相当于预处理降低后续操作难度。但是对于不同的问题，排序的方式可能不同。
实例2：跳跃问题
贪心算法可以理解为一种特殊的动态规划问题，拥有一些更特殊的性质，可以进一步降低动态规划算法的时间复杂度。
跳跃游戏1：
leet55.数组的位置代表跳跃到的位置，数组每个位置的数字代表在那个位置处最远可以跳几步，判断是否可以到达最后一个位置。
本题其实有个关键点在于每个位置上的数字 代表的是 最远可以跳几步，也就是说，也可以不跳那么远，这导致的一点就是，我们的递归/动态规划/贪心都是 分步的，就像这里跳第一下到哪，跳第二下到哪，跳第三下到哪........，我们可以在每一步选择跳到最远处（比如是h位置），同时对之前的每一步进行遍历求其下一步最远能到哪（比如说g位置），当遍历到当前所在位置时，就可以直接跳到最远处g，虽然按照题目是无法从h跳到g，而是得从h之前的某个位置跳到g，但因为之前能跳到h，就说明可以跳到h之前的某个位置，那么g也就是可以跳到的，虽然改动了之前所作的选择，但是并不影响答案，某种程度上自动更新了之前的策略。
leet55 是个相对简单的问题，判断能否跳到最后一个位置，只需要判断任何时候的 可达到的最远距离 能否达到或超过最远距离。当然这里还有一个点是在某个位置处的值为0，那么就会卡住，也就跳不到了，这里是个优化，但对于第一个值就是0的时候，得靠这个判断来输出false。
class Solution {
public boolean canJump(int[] nums) {
int n=nums.length;
int longest=0;
for(int i=0;i<n-1;i++){
longest=Math.max(longest,i+nums[i]);
if(longest<=i){
return false;
}
}
return longest>=n-1;
}
}
有关动态规划的问题，大多是让你求最值的，比如最长子序列，最小编辑距离，最长公共子串等等等。这就是规律，因为动态规划本身就是运筹学里的一种求最值的算法。那么贪心算法作为特殊的动态规划也是一样，一般也是让你求个最值。
leet45.跳跃问题2
这题和上题的最基本思路一样。本题基本的动态规划方法和贪心都可以用，但是动态规划会超时间。
动态规划本质上就是一种遍历，dp可以是dp(nums,p)，表示在位置p时，到最末端所需要的最小步数；那么对于位置p的数组 为nums[p]，对于1到nums[p], 进行遍历，即dp=Math.min(dp[p],1+dp[p+j]) (j属于1到nums[p]) 的范围。这是最基本的动态规划，但很明显是指数型的量。会超时。
那么这里还是利用上一题的贪心算法来进行，现在的问题是，保证你一定可以跳到最后一格，请问你最少要跳多少次，才能跳过去？
贪心算法比动态规划多了一个性质：贪心选择性质。
刚才的动态规划思路，不是要穷举所有子问题，然后取其中最小的作为结果吗？核心的代码框架是这样：
int steps = nums[p];
// 你可以选择跳 1 步，2 步...
for (int i = 1; i <= steps; i++) {
// 计算每一个子问题的结果
int subProblem = dp(nums, p + i);
res = min(subProblem + 1, res);
}
for 循环中会陷入递归计算子问题，这是动态规划时间复杂度高的根本原因。
但是，真的需要「递归地」计算出每一个子问题的结果，然后求最值吗？直观地想一想，似乎不需要递归，只需要判断哪一个选择最具有「潜力」即可：
显然应该跳 2 步调到索引 2，因为nums[2]的可跳跃区域涵盖了索引区间[3..6]，比其他的都大。如果想求最少的跳跃次数，那么往索引 2 跳必然是最优的选择。
你看，这就是贪心选择性质，我们不需要「递归地」计算出所有选择的具体结果然后比较求最值，而只需要做出那个最有「潜力」，看起来最优的选择即可。
换句话说，这正是上一题的分析，对于每一次选择，我们都选择 能跳到的最远距离，这里的i是用于遍历，或者说说是为了计算nums[i]+i的，end是代表每次做出的选择，当遍历到end时就要做出下一次选择，farthest就是下一次选择。整个流程是，end代表当前做出的选择，也就是跳到的位置，i则是遍历并且记录能跳到的最远距离farthest，当遍历到end处时，表示对当期的所有情况都统计完了，又要跳出新的一步，jump用于统计步数，jump++，end则做出选择，跳到farthest处，即最远距离处。
class Solution {
public int jump(int[] nums) {
int jump=0;
int end=0;
int farthest=0;
int n=nums.length;
for(int i=0;i<n-1;i++){
farthest=Math.max(farthest,nums[i]+i);
if(end==i){
jump++;
end=farthest;
}
}
return jump;
}
}
使用贪心算法的实际应用还挺多，比如赫夫曼编码也是一个经典的贪心算法应用。更多时候运用贪心算法可能不是求最优解，而是求次优解以节约时间，比如经典的旅行商问题。
不过我们常见的贪心算法题目，就像本文的题目，大多一眼就能看出来，大不了就先用动态规划求解，如果动态规划都超时，说明该问题存在贪心选择性质无疑了。