45.leetcode题目讲解（Python）： 跳跃游戏 II

我们可以认为“ 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版 持续更新）

我的博客里还有其他好东西： 苔原带