45. 跳跃游戏 II

https://leetcode-cn.com/problems/jump-game-ii/

解法一：穷举

but超时

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        self.jumps = []  #记录所有的跳跃次数
        self.func(nums, 0, 0)
        return min(self.jumps)

    def func(self, nums, pos, count):  #pos为跳跃位置，count为计数
        if pos >= len(nums) - 1:
            self.jumps.append(count)
        else:
            for i in range(nums[pos], 0, -1):
                self.func(nums, pos+i, count+1)

解法二：贪心

i从0开始遍历，每次前移一位，直到n-2即可。

用两个指针迭代，end指向当前能到达的距离，另一个指针farthest向前探测[i,end]所能到达的最远距离。（若不用end保证能到达的距离，则可能出现跳步，然而本题是不能跳的，每一处都必须能到达）

当i到达end时，表示走完一步，jumps加1，end更新为farthest。

在i==0时，jumps就为1（为何？）出发就开始累计步数，因为终点可能大于数组长度，不一定能到达，所以不应该在终点才算一步，而在起点

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0    #步数
        end = 0    #当前能到达的距离
        farthest = 0    #向前探测[i,end]所能到达的最远距离
        for i in range(len(nums)-1):
            farthest = max(i+nums[i], farthest)    #更新最远距离
            if i == end:    #走了一步
                end = farthest    #更新能到达的距离
                jumps += 1
        return jumps