写在前面
贪心算法说简单也简单，因为找到局部的最优解就可以了，说难也确实不是很好想，因为这种思想在想的时候总会有种不那么确定的感觉，想证明的话又会变得很复杂，虽然不需要证明，但是总是不太敢写。
题目一
核心思路
这种类型的题如果当做模拟来做的话，还是比较好写的，不过起码需要O(n²)的复杂度，显然是不想接受的。
观察题目跳跃的规则，可以发现，如果 i 位置可达，那么从 i 到 i + nums[i] 中间的下标都是可达的，那么只要存储当前最远能到达的位置max，比较max与i + nums[i]的大小更新max，这样就能找到最远跳到的位置，不过如果当前遍历到的位置i已经是不可达的了，就显然不能到达最后一个位置，因此此时应该返回false，期间遍历的位置都是可达的，那么最终返回true即可。
图示
代码
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int max = 0;
for(int i = 0; i < n && max < n; i++){
if(i > max){
return false;
}else{
max = Math.max(max, i + nums[i]);
}
}
return true;
}
}
题目二
核心思路一 - 动态规划
跳跃游戏Ⅱ与Ⅰ规则虽然没变，但是需要求解的结果变了很多，不再是只要能到达数组最后即可，而是默认能到，需要求最小的跳跃步数。实话说，我做完第一题做的这道，想了一会儿还是没什么贪心的思路，而是想要使用一个数组然后动态规划来解决，虽然动态规划实际上与贪心算法很像，但是我还是没有那种思路，还需要一点点的积累。
定义一个数组counts[i]来记录开头位置最少需要几步到达i位置，那么对于counts[i]，从下标i + 1到i + nums[i]都等于count[i] + 1，不过这中间访问的位置可能是下标i之前的下标就访问过的，所以可以取一个最小值，不过其实没有必要，因为前边更新过的数一定比当前i更新的数值小，所以可以备份一个max值，表示之前一条最远能跳到的位置，只有i + nums[i]大于max时，才需要更新counts，于是我们可以得到下边这样的代码。
图示
代码
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int index = 0;//当前遍历的下标
int max = 0;//前一跳的最远距离
int[] counts = new int[n];//最短需要跳的步数
while (index < n) {
int temp = index + nums[index];
if (temp > max) {
for (int i = max + 1; i <= temp && i < n; i++) {
counts[i] = counts[index] + 1;
}
max = temp;
}
index++;
}
return counts[n - 1];
}
}
虽然可以较高效的解决问题，但是需要额外使用O(n)的空间。
核心思路二 - 贪心
既然想要贪心，想要跳的步数少，那么每一步就要跳的尽量远，而最远的地方就是i+nums[i]，所以直到遍历到前一步能跳的最远的位置时，才去考虑下一步，这样到终点时就会有两种情况，一是刚好前一步的结尾是终点，二是前一步已经越过终点了，这两种情况的结果会差一，可以分类讨论，不过可以更巧妙，也就是直接忽略最后的终点位置，因为题目保证了可以到达，我们只遍历到倒数第二个位置就已经可以保证到终点了，这样就省去了额外的判断。
代码
class Solution {
public int jump(int[] nums) {
int end = 0;//上一跳能跳到的最远位置
int max = 0; //当前最远的位置
int count = 0;//总跳数
for(int i = 0; i < nums.length - 1; i++){
max = Math.max(max, nums[i] + i);
if(i == end){
end = max;
count++;
}
}
return count;
}
}
总结
虽然之前也写过几道贪心题，但是这种思想还是很不好理解，还是需要好好的训练一下啊。
