跳跃游戏问题：如何判断是否能跳跃到数组的最后一个位置

如何判断是否能跳跃到数组的最后一个位置

引言

在这篇博客中，我们将探讨一个经典的算法问题：跳跃游戏。这个问题在算法面试中非常常见，并且有多种解法。我们会一步步分析问题，最终找到解决方案。

问题描述

给你一个非负整数数组 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 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

解法分析

这个问题可以通过动态规划或者贪心算法来解决。我们将在下面分别介绍这两种解法。

动态规划解法

动态规划的核心思想是记录每个位置能否到达。我们可以用一个布尔数组 dp 来表示，从起点能否到达某个位置。dp[0] 初始化为 true，然后依次更新 dp 数组中的值。

代码实现：

Java

public class Solution {
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;

        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[nums.length - 1];
    }
}

Python

def canJump(nums):
    dp = [False] * len(nums)
    dp[0] = True

    for i in range(1, len(nums)):
        for j in range(i):
            if dp[j] and j + nums[j] >= i:
                dp[i] = True
                break

    return dp[-1]

贪心算法解法

贪心算法的核心思想是维护一个可以到达的最远位置。我们从第一个位置开始，依次更新能到达的最远位置。如果在遍历过程中，最远位置已经大于等于数组的最后一个位置，则说明可以到达最后一个下标。

代码实现：

Java

public class Solution {
    public boolean canJump(int[] nums) {
        int maxReachableIndex = 0;

        for (int i = 0; i < nums.length; i++) {
            // 如果我们已经到达了不可达的位置，返回false。
            if (i > maxReachableIndex) {
                return false;
            }

            // 更新最大可达位置。
            maxReachableIndex = Math.max(maxReachableIndex, i + nums[i]);
        }

        // 如果我们没有返回false，那么就可以到达最后一个位置。
        return true;
    }
}

Python

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)
    return True

结论

通过上述两种解法，我们可以有效地判断是否能够从数组的第一个位置跳跃到最后一个位置。动态规划方法比较直观，但时间复杂度较高；而贪心算法更为高效，适用于较大规模的数据。

希望这篇博客能帮助你更好地理解跳跃游戏问题及其解决方法。如果你有其他更好的解法，欢迎在评论区分享！

参考文献

• LeetCode: Jump Game
• 动态规划与贪心算法的详细解释