每日算法 — 使用java实现跳跃游戏：贪心策略与动态规划的最优解分析

跳跃游戏是数组贪心算法的经典入门问题，也是各大算法面试中的高频考点。问题描述简洁却蕴含深刻：给定一个非负整数数组，每个元素表示你在该位置可以跳跃的最大长度，判断你是否能够从数组第一个位置跳到最后一个位置。

这个问题的精妙之处在于，它存在从动态规划到贪心策略的优雅优化路径，完美展示了算法设计中”去冗余”的艺术。本文将用Java实现跳跃游戏系列问题，从基础的可达性判断，到最少跳跃次数求解，完整呈现算法演进过程。

问题一：跳跃游戏 I — 可达性判断

给定数组 nums，nums[i] 表示从位置i最多可以向右跳跃 nums[i] 步。判断是否能到达最后一个下标。

动态规划思路

最直观的想法是用动态规划：dp[i] 表示能否到达位置i。对于每个位置j < i，如果 dp[j] 为真且 j + nums[j] >= i，则 dp[i] = true。

    /**
     * 动态规划解法：判断是否能到达最后一个位置
     * 时间复杂度 O(n^2)，空间复杂度 O(n)
     */
    public boolean canJumpDP(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;

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

贪心优化：维护最右可达边界

动态规划解法中，内层循环存在大量冗余判断。关键观察是：我们不需要知道每个位置是否可达，只需要知道当前能到达的最右边界。

设 maxReach 为当前能够到达的最远位置。遍历数组时，如果当前位置 i <= maxReach，说明位置i是可达的，此时更新 maxReach = max(maxReach, i + nums[i])。如果某时刻 maxReach >= n - 1，说明可以到达终点。

    /**
     * 贪心解法：维护最右可达边界
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public boolean canJumpGreedy(int[] nums) {
        int n = nums.length;
        int maxReach = 0; // 当前能到达的最远位置

        for (int i = 0; i < n; i++) {
            // 如果当前位置已经超出可达范围，直接返回false
            if (i > maxReach) {
                return false;
            }
            // 更新最远可达位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 提前终止：已经可以到达终点
            if (maxReach >= n - 1) {
                return true;
            }
        }
        return true;
    }

贪心解法的优雅在于：它将时间复杂度从O(n²)降到了O(n)，空间复杂度从O(n)降到了O(1)。这是通过丢弃不必要的中间状态信息实现的——我们只需要一个标量 maxReach，而非整个DP数组。

问题二：跳跃游戏 II — 最少跳跃次数

进阶版本：假设你一定可以到达最后一个位置，求到达终点的最少跳跃次数。

动态规划思路

dp[i] 表示到达位置i的最少跳跃次数。对于每个位置j < i，如果 j + nums[j] >= i，则 dp[i] = min(dp[i], dp[j] + 1)。

    /**
     * 动态规划解法：求最少跳跃次数
     * 时间复杂度 O(n^2)，空间复杂度 O(n)
     */
    public int jumpDP(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }

贪心优化：维护当前步边界与下一步边界

同样可以用贪心优化到O(n)。核心思想是：在当前步数能到达的范围内，找出下一步能到达的最远位置。

设 currentEnd 为当前步数能到达的最右边界，farthest 为下一步能到达的最远边界。当遍历到 currentEnd 时，必须再跳一步，将 currentEnd 更新为 farthest。

    /**
     * 贪心解法：维护当前步边界与下一步最远距离
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public int jumpGreedy(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;

        int jumps = 0;          // 已用跳跃次数
        int currentEnd = 0;     // 当前步数能到达的最右边界
        int farthest = 0;       // 下一步能到达的最远位置

        for (int i = 0; i < n - 1; i++) {
            // 更新下一步能到达的最远位置
            farthest = Math.max(farthest, i + nums[i]);

            // 到达当前步的边界，必须再跳一步
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                // 提前终止
                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }
        return jumps;
    }

完整可运行代码

import java.util.*;

/**
 * 跳跃游戏求解器
 * 包含两个经典问题：可达性判断与最少跳跃次数
 */
public class JumpGameSolver {

    // ========== 问题一：跳跃游戏 I - 可达性判断 ==========

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

    public boolean canJumpGreedy(int[] nums) {
        int n = nums.length;
        int maxReach = 0;
        for (int i = 0; i < n; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= n - 1) return true;
        }
        return true;
    }

    // ========== 问题二：跳跃游戏 II - 最少跳跃次数 ==========

    public int jumpDP(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }

    public int jumpGreedy(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;
        int jumps = 0, currentEnd = 0, farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                if (currentEnd >= n - 1) break;
            }
        }
        return jumps;
    }

    // ========== 演示与测试 ==========

    public void demonstrate() {
        int[][] testCases = {
            {2, 3, 1, 1, 4},      // 可达，最少2跳
            {3, 2, 1, 0, 4},      // 不可达
            {2, 0, 0},            // 可达，最少1跳
            {1, 1, 1, 1},         // 可达，最少3跳
            {5, 4, 3, 2, 1, 0},   // 可达，最少1跳
        };

        for (int[] nums : testCases) {
            System.out.println("数组: " + Arrays.toString(nums));
            boolean can = canJumpGreedy(nums);
            System.out.println("  是否可达: " + can);
            if (can) {
                System.out.println("  最少跳跃次数: " + jumpGreedy(nums));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        new JumpGameSolver().demonstrate();
    }
}

算法复杂度对比

贪心正确性证明

跳跃游戏II的贪心策略为什么正确？关键在于：

当我们遍历到 currentEnd 时，所有在 [0, currentEnd] 范围内的位置都已经在 jumps 步内可达。而 [currentEnd+1, farthest] 范围内的位置需要 jumps+1 步才能到达。选择 farthest 作为下一步边界，保证了我们在每一步都最大化了覆盖范围，因此跳跃次数最少。

这是典型的”贪心选择性质”——局部最优（每步跳到最远）导致全局最优（总步数最少）。

扩展思考

跳跃游戏的框架可以扩展到多维空间（如机器人网格路径规划）、带代价的版本（每次跳跃消耗不同能量）、以及障碍物版本（某些位置不可达）。核心的贪心思想——维护可达边界——在这些问题中依然适用。