Jump Game问题求助：代码部分测试用例通过但提交失败

你的代码存在的两个核心问题 #

• 循环赋值逻辑错误：在for循环中，你每次将ans直接覆盖为当前递归的返回值，这会导致如果前面的递归分支已经返回true，但后续分支返回false时，ans会被错误覆盖为false，最终漏掉正确的可达路径。比如当前位置能跳3步，第一步就到终点返回true，但循环继续执行后续步数，若后续分支返回false，ans就会被改成false，导致最终返回错误结果。
• 无记忆化的递归会超时：对于较大的数组，递归会重复计算大量相同位置的状态，时间复杂度达到O(2^n)，很容易超出时间限制。

修复后的递归版本（添加记忆化） #

通过记忆数组记录已计算过的位置状态，避免重复递归：

class Solution {
    // 记忆数组：0=未计算，1=可达，2=不可达
    int[] memo;
    public boolean canJump(int[] nums) {
        memo = new int[nums.length];
        return helper(nums, 0);
    }
    public boolean helper(int[] nums, int currentPointer){
        if(currentPointer == nums.length - 1) {
            return true;
        }
        // 已计算过的位置直接返回结果
        if(memo[currentPointer] != 0) {
            return memo[currentPointer] == 1;
        }
        // 遍历所有可能的跳跃步数，只要有一条路径可达就返回true
        for(int i = 1; i <= nums[currentPointer]; i++) {
            int next = currentPointer + i;
            if(next < nums.length && helper(nums, next)) {
                memo[currentPointer] = 1;
                return true;
            }
        }   
        // 所有路径都不可达，记录状态并返回false
        memo[currentPointer] = 2;
        return false;
    }
}

更高效的贪心算法（最优解） #

递归加记忆化的时间复杂度为O(n)，但贪心算法可以做到一次遍历，空间复杂度O(1)，思路是维护当前能到达的最远位置：

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        int n = nums.length;
        for(int i = 0; i < n; i++){
            // 当前位置超出最远可达范围，直接返回false
            if(i > maxReach){
                return false;
            }
            // 更新最远可达位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 最远可达位置覆盖终点，直接返回true
            if(maxReach >= n - 1){
                return true;
            }
        }
        return true;
    }
}

贪心算法核心逻辑 #

• 遍历数组时，持续更新当前能到达的最远位置maxReach。
• 如果遍历到某个位置时，该位置超出maxReach，说明无法到达此处，自然也到不了终点。
• 一旦maxReach大于等于数组最后一个索引，直接返回true，因为已经可以到达终点。

内容的提问来源于stack exchange，提问作者Tarun gujral