45. 跳跃游戏 II

思路

贪心策略： 用end来代表当前区间最后一个位置，maxp来代表可到达的最大位置，当区间遍历结束后，知道这个区间里有个下标可以跳跃至最远（即maxp）（贪心：每次都要选最远的跳） 那此时应该要更换区间范围.进行更换即代表走一步
如 [2,3,1,1,4] 刚开始区间【0】，当遍历区间结束，能到达最远距离是下标2，更换end为maxp,即到下标2。不论是从下标0到1或者2，都是需要走一步。
下标0这个位置可以跳到下标2 在区间[3,1]中，当遍历到下标2时发现 ，1下标可以跳到最远，那选择的跳跃应该是0下标到1，1到下一个位（maxp） （所说的下标均指列表nums的下标）

class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""#dp方法 类似找零钱  超限# dp =[0]*(len(nums))# for i in range(1,len(nums)):#     j = i# 走的步骤不可能大于n-1#     mins = len(nums)#     while j>0:#         if (j-1) +nums[j-1]>=i:#             mins=min(min,dp[j-1])#         j-=1#     dp[i]=mins+1# return dp[-1]if len(nums)==1:return 0endp = 0maxp = 0step = 0for i in range(len(nums)-1):maxp = max(maxp,i+nums[i])if i == endp:endp=maxpstep+=1#遍历至n-2时，还没走到nif endp<len(nums)-1:step+=1return step