55.Jump Game 2

题目地址

主要思路：

跳跃问题其实是一个广度优先搜索问题。（遍历到的节点都保证是该层能得到的最多定点也就是确保高度最低。），对每一层都遍历，得到一个（start, end）集合，再继续遍历。可以看到每一个点都计算过，但是没有重复计算。同时广度优先的策略保证得到的最终点的level是最小的level，也就是代码中的step。

代码：

def jump(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n, start, end, step = len(nums), 0,0,0
    while end<n-1:
        step += 1
        maxend = end + 1
        for i in range(start, end+ 1):
            if i + nums[i] >= n -1:
                return step
            maxend = max(maxend, i + nums[i])
        start, end = end + 1, maxend
    return step