题目大意：
跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
这道题需要使用贪心算法。试想，如果想使用最少步数跳跃到最后一位，那么我们每一步都需要尽量跳的远一些。如果想要保证每一步都要跳的尽量远，那么必将需要牺牲一些局部利益来保障全局利益最大化。我们先看当前位置能够跳到的范围，比如当前位置是i，那么从第i位能跳到的范围应该是[i+1, i+nums[i]]。显然，这个范围越大，我们下一步的选择就越多，并且我们距离终点也就越近，因此，当范围右端不是终点的前提下，下一步的最优解应该是范围内能跳到最远距离的点。注意能跳到最远距离的点不仅取决于nums[i]，也取决于i。比如区间范围是[10, 15]，其中nums[10]=5, nums[14]=4，虽然nums[10]大于nums[14],但从位置10我们最多能跳到15，而从位置14我们可以跳到18，因此下一步跳跃到14更好一些（相对10来说，实际解题时我们还需查看下标11，12和15的值）。
实现代码：
public int jump(int[] nums) {
int res=0; // 步数
int index=0; // 当前位置
while(index<nums.length-1){
int n=nums[index]; // 当前可跳跃的距离
int left=index+1; // 跳跃范围的左边界
int right=index+n; // 跳跃范围的右边界
int max=0; // 跳跃范围内的所有点中，能够跳跃最远的点
// 如果有边界已经超越了终点，返回
if(right>=nums.length-1) return res+1;
// 查看范围内每一个点
for(int i=left;i<=right;i++){
// 如果当前位置加上跳跃距离能够到达更远的距离
if(i+nums[i]>=max){
max=i+nums[i]; // 更新最远距离
index=i; // 更新下一步为该坐标
}
}
res++;
}
return res;
}本题解法执行时间为2ms。
Runtime: 2 ms, faster than 44.46% of Java online submissions for Jump Game II.
Memory Usage: 42.1 MB, less than 5.77% of Java online submissions for Jump Game II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-45-jump-game-ii-解题思路分析/