本文共 2123 字，大约阅读时间需要 7 分钟。
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例:
输入: [2,3,1,1,4]
输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明:假设你总是可以到达数组的最后一个位置。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最常见的思路是从0出发，然后在能力范围内不断跳跃，直到跳到最后；这样的思路下，该问题可以使用递归的方法处理；但是实际上，这是一种暴力解法：访问完所有可能的结果并计算出最优结果；以下为该思路的一个实现，运行超时，倒在最后一个测试用例上；
private int[] buffer;public int jump(int[] nums) { if(nums.length==1){ return 0; } buffer=new int[nums.length]; return jumpHelper(nums,0);}private int jumpHelper(int[] nums,int start){ if(buffer[start]!=0){ return buffer[start]; } if(nums[start]+start>=nums.length-1){ buffer[start]=1; return 1; }//从start到end只需要1次跳跃即可 int minTimes=Integer.MAX_VALUE; boolean hasArrived=false; int tempTimes; int nextStart; int capacity=nums[start]; for(int i=1;i<=capacity;i++){ nextStart=start+i; if(nextStart tempTimes){ minTimes=tempTimes; hasArrived=true; } }else{ break; } } if(hasArrived) { buffer[start] = minTimes + 1; return minTimes + 1; }else{ return -1; }} //解法Apublic int jump(int[] nums) { int step = 0; int right = 0; int cur = 0; while (right < nums.length-1) { int newRight = right; while (cur <= right) { newRight = Integer.max(nums[cur] + cur, newRight); cur++; } right = newRight; step++; } return step;}//解法Bpublic int jump(int[] nums){ int next_r=nums[0]; int numsSize=nums.length; int r=next_r; int jump=0; for(int i=1;i 解法A和解法B思路是一样的；如果要想尽可能快得到达终点，那么每一步跳跃后，下一步跳跃能达到的位置要尽可能的远；为了找到这个点，我们需要遍历完当前跳跃所能覆盖范围内的点；
递归解法之所以超时，是因为，对于每个点，该方法都进行了跳跃尝试，而这些点能不能产生最小跳跃值并不是在达到终点时才能得到——通过计算就能得到选择该点作为落脚点时，下一跳最远可到的位置；
算法之所以不好，一定是做了无用功——对最后结果没有贡献的计算（不用做，但是却做了）；
当我们看到题目后，有可能会马上想到解决方法；此时就要对题目进行深入的理解，看能否简化自己的方法，判断自己方法中对题目有贡献的是那些，没有贡献的是那些；如何保留，如何剔除；
本题生动体现了“走一步，看一步”的智慧，而这用比较专业的术语解释即为：贪心算法；贪心解法的正确性是需要逻辑推理和证明的；所以，编程和数学紧密相关；