代码随想录算法训练营-回溯算法-2|55. 跳跃游戏、45. 跳跃游戏 II、1005. K 次取反后最大化的数组和-526互联

1. 跳跃的覆盖范围。这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

2. 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

时间复杂度: O(n)
空间复杂度: O(1)

 1 class Solution:
 2     def canJump(self, nums: List[int]) -> bool:
 3         cover = 0
 4         if len(nums) == 1: return True
 5         i = 0
 6         # python不支持动态修改for循环中变量,使用while循环代替
 7         while i <= cover:
 8             cover = max(i + nums[i], cover)
 9             if cover >= len(nums) - 1: return True
10             i += 1
11         return False

45. 跳跃游戏 II

1. 目标是使用最少的跳跃次数到达数组的最后一个位置。

2. 说明: 假设你总是可以到达数组的最后一个位置。

3. 这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

时间复杂度: O(n)
空间复杂度: O(1)

 1 class Solution:
 2     def jump(self, nums):
 3         if len(nums) == 1:
 4             return 0
 5         
 6         cur_distance = 0  # 当前覆盖最远距离下标
 7         ans = 0  # 记录走的最大步数
 8         next_distance = 0  # 下一步覆盖最远距离下标
 9         
10         for i in range(len(nums)):
11             next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖最远距离下标
12             if i == cur_distance:  # 遇到当前覆盖最远距离下标
13                 ans += 1  # 需要走下一步
14                 cur_distance = next_distance  # 更新当前覆盖最远距离下标（相当于加油了）
15                 if next_distance >= len(nums) - 1:  # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束
16                     break
17         
18         return ans