Leetcode Link: 45. 跳跃游戏 II - 力扣（LeetCode）
题目
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
解法一
思路：非常典型的贪心算法
贪心的点在于：每次都在当前能走的范围内选择下一步走的最远的步数。
拿例 1 举例：
在 0 位置的时候，能够走到的最大范围 (nums[0]=2) 是[0, 1, 2]，在这个范围里，找到能走的最远的那个位置。
显然位置 1 对应走 3 步，能够走到 4，是最远的位置，所以在 0 位置的时候就走到 1。
题解：
class Solution:
def jump(self, nums: List[int]) -> int:
# 上次走的点和上次走的最远的范围
# 在这个范围里选择能走的最远点
last_p = 0
last_cover = nums[0]+0
max_cover = last_cover
step = 0
while(last_p<(len(nums)-1)):
# 在这个范围里选择能走的最远点
for p in range(last_p+1, last_cover+1):
if p >= (len(nums)-1): # 溢出，走到了末尾
cur_p = p
break
if nums[p]+p > max_cover: #当前点走的更远，就更新
max_cover = nums[p]+p
cur_p = p
last_p = cur_p
last_cover = max_cover
step += 1
return step相同思路题解的说法 遍历数组，更新当前位置所能到达的最远位置记为 end，边走边更新最远位置 maxPosition，当到达 end 时记为一步，并更新 maxPosition
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
end = 0
step = 0
maxPosition = 0
for i in range(n - 1):
maxPosition = max(maxPosition, i + nums[i])
if i == end:
step += 1
end = maxPosition
return step这个解法不是很直观
解法二
思路：开始的时候想使用回溯，并且写出了代码。如题解
然而每次都走最大步不一定能够得到正确答案，可以尝试一下提交，题目中的例子 [2,3,1,1,4] 就是错的。
题解：
class Solution:
def jump(self, nums: List[int]) -> int:
def backtracking(p):
# p 是即将跳到的位置
nonlocal cover, step
if cover >= len(nums)-1:
return True
step += 1
# 在该点每次都走最大步
for val in range(nums[p], 0, -1):
cover = cover + val
if backtracking(p+val):
return True
cover = cover - val
cover = 0
step = 0
backtracking(0)
return step