Leetcode45 跳跃游戏 II

给定一个长度为 n 的非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该下标可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个下标。

先确定跳跃的范围，假设当前下标为 i，那么可以跳跃到的下标范围是 [i+1, i+nums[i]]。如果 i+nums[i] 大于等于最后一个下标 n-1，那么就可以直接到达最后一个下标。这个时候更新最后的下标为 i，并且跳跃次数加一。接下来继续从新的下标 i 开始，直到最后一个下标为 0。

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 递归
        # n = len(nums)
        # if n == 1:
        #     return 0 
        # for i in range(0, n-1):
        #     jump_len = nums[i]
        #     if jump_len + i >= n-1:
        #         return self.jump(nums[:i+1]) + 1 
        
        # 迭代
        n = len(nums)
        last, count = n-1, 0
        while last > 0:
            for i in range(0, last):
                if i + nums[i] >= last:
                    count += 1
                    last = i
                    break
        return count