力扣热题100_贪心算法_55_跳跃游戏

文章目录

• 题目链接
• 解题思路
• 解题代码

题目链接

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

解题思路

    # 参考贪心算法
    # 贪心算法 与 动态规划算法的区别 ：
    # 贪心算法
        # 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留；
        # 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
    # 动态规划算法：
        # 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；
        # 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解；
        # 3.边界条件：即最简单的，可以直接得出的局部最优解。

解题代码

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i, num in enumerate(nums):
            #print("1.i, num:", i, num)
            #print("2.reach:", reach)
            if i > reach:
                return False
            #print("3.i + num:", i + num)
            reach = max(reach, i + num)
            #print("4.reach:", reach)
        return True

参考资料：博客园–负雪明烛