力扣Leetcode：45. 跳跃游戏 II（Python）
题目链接
https://leetcode-cn.com/problems/jump-game-ii/
题目描述
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
思路
在前一篇文章中实现了动态规划算法。若数组长度为N，数组元素平均大小为M，则时间复杂度为O(MN)。
下面我们将该算法优化至O(N)，即仅遍历一遍。使用贪心思想，在当前位置向后跳时，选择再下一步能够达到最远的（潜力最大的）。即若当前位置为curr，可以选择的下一个位置为i，则选择i+nums[i]最大的位置。可以反证之。这样仅需要遍历一次数组。
代码
class Solution:
def jump(self, nums) -> int:
curr, jump_time = 0, 0
while curr < len(nums)-1:
# move to the best position
best_pos, best_val = curr, 0
for step in range(1, nums[curr]+1):
# reach the end
if curr + step >= len(nums)-1:
best_pos = curr + step
break
if curr + step + nums[curr + step] > best_val:
best_val, best_pos = curr + step + nums[curr + step], curr + step
curr, jump_time = best_pos, jump_time + 1
return jump_time
s = Solution()
print(s.jump([2, 3, 1, 1, 4]))
print(s.jump([2, 3, 0, 1, 4]))