题目
Jump Game II - LeetCode
我们可以认为“ nums”中每个项目的数字代表一个覆盖区域。 因此，为了解决这个问题，我们希望用最少的区域覆盖整个范围。值得注意的是，这我们虽然把这种算法称为贪婪算法，一般而言，贪婪算法找出的不是最优解。但是，在这道题目中，覆盖最远的下个区域是相比其他区域而言是占优策略Strategic dominance, 所以，在这道题目中，我们是可以通过贪婪得到最优解的。
算法的思路如下：
1.根据当前位置及其区域，找到范围从i 到（i + num）的相邻区域。
2.将这些区域的最远覆盖范围与最大范围进行比较：如果（i + num）大于最大范围，则设置下一个覆盖范围从r开始，最大范围等于i + num。
3.将当前位置更新为r。
4.继续这样做，直到覆盖整个区域。
class Solution:
def jump(self, nums) -> int:
if not nums or len(nums) == 1:
return 0
des = len(nums) - 1
res = 0
i = 0
max_range = 0
nxt = 0
while i < des:
if i + nums[i] >= des:
return res + 1
for r in range(i + 1, i + nums[i] + 1):
if r + nums[r] > max_range:
max_range = r + nums[r]
nxt = r
i = nxt
res += 1
如何刷题 : Leetcode 题目的正确打开方式
我的GitHub : Jedi-XL
其他题目答案：leetcode题目答案讲解汇总（Python版 持续更新）
我的博客里还有其他好东西： 苔原带
