小哆啦的跳跃挑战：能否突破迷宫的极限？

小哆啦开始力扣每日一题的第六天

https://leetcode.cn/problems/jump-game/description/

小哆啦的跳跃挑战：能否突破迷宫的极限？

第一阶段：小哆啦的初次尝试 —— 盲目跳跃

小哆啦刚进入跳跃之城，他决定采用一种非常直接的方法来解决问题——每次都跳得尽可能远。于是，他写下了第一版算法：

def canJump(nums):
    for i in range(len(nums)):
        if i + nums[i] >= len(nums) - 1:
            return True
    return False

在这段代码中，他做了一个简单的判断：如果当前位置加上该位置的跳跃长度大于等于终点位置，直接返回 True。但是，问题来了——这种方法过于直白，并且没有考虑到每一步的实际可行性。

第二阶段：问题的暴露 —— 无法突破迷宫

小哆啦兴冲冲地运行了第一版代码，然而，跳跃过程中的一些难题很快显现出来。

假设迷宫的数字是这样的：

nums = [2, 3, 1, 1, 4]

小哆啦的算法会错误地认为他可以直接从起点跳跃到终点，但事实上，在第四步时，他的跳跃长度不足以抵达终点。代码虽然看似简单，但其实并没有判断是否每一步的选择都是可行的。于是，他陷入了困境。

第三阶段：小哆啦的反思 —— 引入贪心算法

意识到问题后，小哆啦开始进行反思。他决定尝试一种更为有效的方法：贪心算法。具体来说，贪心算法的核心思想是：始终保持当前能够跳跃到的最远位置，直到突破终点。

他调整了代码：

def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

这段代码的思想是：在每一步，更新当前能够跳到的最远位置 max_reach，如果当前的位置超出了 max_reach，说明无法继续前进，返回 False。否则，继续更新最远可达位置，直到找到能够到达终点的路径。

第四阶段：算法的优化 —— 精益求精

小哆啦很高兴地发现，新的算法有效地解决了迷宫中的问题。可是，他并没有止步于此。经过深入思考，他意识到可以进一步优化他的算法，使其更加高效。他优化了代码的细节，去除了不必要的判断，改进了代码结构：

def canJump(nums):
    max_reach = 0
    for i, num in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + num)
        if max_reach >= len(nums) - 1:
            return True
    return False

优化后的算法不仅更加简洁，而且在发现能够到达终点时，立即返回 True，避免了不必要的计算。

第五阶段：最终的突破 —— 完美解决问题

通过这次改进，小哆啦成功地突破了跳跃之城的挑战。他的贪心算法能够精确计算每一步，确保他能够在任何情况下都能找到通向终点的路径。

# 测试案例
nums1 = [2, 3, 1, 1, 4]  # True
nums2 = [3, 2, 1, 0, 4]  # False
print(canJump(nums1))  # 输出：True
print(canJump(nums2))  # 输出：False

通过精心设计的贪心算法，小哆啦不仅成功到达了终点，还深刻理解了“最远可达”这一概念。他终于明白了，跳跃不仅需要勇气，更需要智慧和策略。