贪心算法
贪心算法可以理解为一种特殊的动态规划为题，拥有一些更加特殊的性质，可以进一步降低动态规划算法的时间复杂度。
来看几道题目熟悉一下这种“不断寻求局部最优”的算法。
跳跃游戏 I
输入一个非负整数数组nums，数组元素nums[i]表示的是：如果你站在位置 i ，最多能够往前跳几步。
现在你站在第一个位置nums[0]，试问你能否跳到数组的最后一个位置?
例：[1,2,3,4,5]，可以
[1,2,0,0,4]，不行
思路分析
这题相对比较简单一些吧，当然不要去用回溯，用回溯的话时间复杂度太高。
成功的方式太多了，但是失败的方式只有一个：有足够多的0横亘在其中，导致不论怎么努力就是跳不过去。
我们哪几个栗子来试一下吧：
[0,····] //点点点的意思是随便你填什么数字都无所谓了
[1,2,1,0,···]
[2,0,0,···]
//还有啥特例吗？
- 1
- 2
- 3
- 4
我们来分析一下上面的栗子（我们假设数组有-1格，nums[-1] = 1，我们从nums[-1]开始）：
第一个栗子：在下标为0的时候遇到了绝望的0，从下标为-1的地方为此前能前进的最大步数1，无法跨越，终结。
第二个栗子：在下标为3的时候遇到了绝望的0，从下标为1的地方获得了此前能前进的最大步数2，无法跨越，失败。
第三个栗子：在下标为2的时候遇到了绝望的0，从下标为0的地方获得了此前能前进的最大步数2，无法跨越，失败。
这三个栗子中，我们能提取出什么有效的信息？
0 -（-1） = 1
3 - 1 = 2
2 - 0 = 2
- 1
- 2
- 3
对吧。
还有呢？为什么不变通一下，比如说例2中，不通过下标为2的点去中转呢？因为中转也无效啊。
那就是说我们要去尝试着中转。
这样讲可能会有点绕啊，我把例2改一下：[1,2,2,0]，这不就活了吗！
拿两个例2来比对一下：
（以flag纪录当前能够到达的最远距离）
[1,2,1,0,···]
//下标0最多到下标1，flag = 1；下标1最多到下标3，flag = 3；下标2最多到下标3，flag = 3；下标3，flag = 3；卒
[1,2,2,0]
//下标0：flag = 1；下标1：flag = 3；下标2：flag = 4
- 1
- 2
- 3
- 4
可以看到，当flag == 下标 的时候，就凉凉了。
代码实现
所以，我们写出代码：
bool canJump(vector<int>& nums){
int n = nums.size();
int farthest = 0;
for(int i = 0; i < n-1; i++){
//不断计算能够跳到的最远距离
farthest = max(farthest,i+nums[i]);
//如果碰到0跳不动了
if(farthest <= i) return false;
}
return farthest >= n-1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
跳跃游戏 II
跟上面差不多，但是这次保证你能跳到最后，问你最少跳几次。
看着好眼熟啊，好像前面写过一道这样的题。换硬币是吧。
去递归选取后续跳法里面的最优，属于一种：从后向前的解法，可以理解为从底层开始层序遍历一棵树。只不过我们后来通过备忘录对这棵树进行了剪枝，不然真的不忍直视啊。
但是呢，我们今天讲的是贪心算法，它可以想象成从上往下一条路走下去。让我们看看：
思路
贪心算法是什么？贪心算法会选择当下最有潜力的一步。
举个例子：[2,3,1,2,5,1]
当你现在在下标0的位置，你可以跳两步。动归的话会递归去算这两步到最终结果的最优步数，但是贪心算法不这样。
贪心算法是每次尽可能多跳吗？NoNoNo，选择当下最有潜力的：在坐标1的位置，你有三个选择；在坐标2的位置，你只有一个选择，所以贪心算法会让你选择跳到坐标1。这就是贪心算法的局部最优（不要奇思妙想啥反例，要用贪心算法，就要承担它的失误率）。
接下来，我们来写代码：
int jump(vector<int>& nums){
int n = nums.size();
//站在索引i，最多能跳到索引end
int end = 0;
//从索引【i···end】起跳，最远能到的距离
int farthest = 0;
//纪录跳跃次数
int jumps = 0;
for(int i = 0; i<n; i++){
farthest = max(nums[i]+1,farthest);
if(end == i){ jumps++; end = farthest;
}
}
return jumps;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
右手中指都麻了。。
歇了歇了。
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/114147353