力扣 跳跃游戏 II
贪心算法，存下每一步的最远，去达到全局的最小跳跃次数。
题目
从题中要达到最少次数，肯定是每一步尽可能走远一点。但注意j被限制了范围，这种不用想每一步遍历时肯定选最大的num[i]，但要注意，题中是可以到达不是刚好到达，因此最后一步只要大于最后一个数都是可以的。从第一个数开始遍历，每一步贪心去选最远的距离，然后每个数都存下一个可达到的最远距离便于更新，因为贪心每一次都是基于当前数的最优，并不是全局最优。
时间复杂度： O(n)，空间复杂度： O(1)。
class Solution {
public int jump(int[] nums) {
int step=0,end=0,furthest=0;
for(int i=0; i<nums.length-1;i++){
furthest = Math.max(furthest, i+nums[i]); //dp每个i，记录每个位置能达到的最远距离
if(i==end){ //i遍历到上个起跳点能到的最远距离
end = furthest; //更新到下一步要跳到的位置，注意这里跳的最远距离由i前面的数贪心选出来的
step++; //跳往下一步，因此最后一个数不用遍历
}
}
return step;
}
}动态规划是存一个要维护状态的dp数组，每次的状态由上几个状态更新得到，这题用dp会很慢。而贪心策略在于，每一步都存下最优状态便于后续的更新。