经典问题---跳跃游戏II（贪心算法）
一、题目描述
跳跃游戏II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1步，然后跳3步到达数组的最后一个位置。
二、思路分析
从下标0开始，第一步只能由nums[0]决定，但不是当前跳的越远越好，nums[0]=2，但实际我们跳到位置1才能达到最小跳跃数。
那么究竟跳几格呢？那就看哪个位置下一步可以跳的更远了，这也就是贪心的思想。我们要不断确定下一步可以到达的最右端点，然后遍历完这一步的最右端点。
题目测试用例都确保可以跳到最后，根据上面的逻辑，走完一步，我们就要遍历这一步所涵盖的区域内，哪个位置能够跳的最远。知道这个最远的位置后，我们也遍历了当前步数可以到达最右端点，那么后面的位置是步数+1的区间，同理我们再遍历这个区间，然后确定下一步能够到的最远距离，直到最后可以遍历完。
例如下表：nums=[1,2,1,1,1] 那么第一步的区间是[0,1]，第二步的区间是[2,3]，第三步的区间是[4,4]。
在遍历第i步的区间我们要尽量确定第i+1步能到达的最远位置
| 第一步 | 第二步 | 第三步 | ||
| 1 | 2 | 1 | 1 | 1 |
三、代码实现
1.dp数组存储
class Solution:
def jump(self, nums: List[int]) -> int:
length = len(nums)
if length == 1:
return 0
right = 1
dp = [0] * length
for i in range(length):
# 需要更新的dp最右端点值
temp = nums[i] + i + 1
for j in range(right,min(temp,length)):
# 将[right,temp]进行染色，也就是设置为下一步的区间
dp[j] = dp[i] + 1
right = max(temp,right)
# 这一步已经可以到达终点
if right >= length:
break
return dp[length-1]2.双指针（更推荐）
效率更高，有更低的空间复杂度。
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
border = 0 # 当前步数的最右端点值
current_right = 0 # 下一步的最右端点值
ans = 0
for i in range(n):
# 更新下一步可以到达的最远位置
current_right = max(current_right, i + nums[i])
# 下一步可以到达终点
if current_right >= n - 1:
return ans+1
# 当前步数的区间遍历结束，要开始下一步
if i == border:
border = current_right
ans += 1
return ans