每日算法 — 使用java实现跳皮筋：跳跃游戏与动态规划

游戏背景与问题建模

跳皮筋是中国传统的儿童游戏，玩家需要在皮筋形成的网格中跳跃前进，规则要求每次跳跃必须踩中特定节点，且不能踩到禁止区域。本文将其抽象为跳跃游戏问题（Jump Game）：给定一个一维数组，每个元素表示从该位置最多可以向前跳跃的步数，判断能否到达终点；若能，求出最少跳跃次数。

该问题是 LeetCode 经典题型，同时也可扩展到二维网格上的最短路径问题。

算法思路

最少跳跃次数：动态规划

设 dp[i] 表示到达位置 i 所需的最少跳跃次数。状态转移方程为：

dp[i] = min(dp[j] + 1)  对所有满足 j + nums[j] >= i 的 j < i

贪心优化：O(n) 解法

维护当前能到达的最远边界（currentEnd）和下一跳能到达的最远边界（farthest）。当遍历到 currentEnd 时，跳跃次数加 1，并将 currentEnd 更新为 farthest。

二维扩展：网格最短路径

在二维网格中，每个格子有最大跳跃距离限制，使用 BFS 配合访问标记求解最短路径。

Java 完整实现

import java.util.*;

/**
 * 跳皮筋：跳跃游戏与动态规划
 * 包含一维最少跳跃、可达性判断、二维网格扩展
 */
public class JumpRope {

    /**
     * 动态规划求解最少跳跃次数
     * @param nums 每个位置的最大跳跃步数
     * @return 到达终点的最少跳跃次数，若无法到达返回 -1
     */
    public int minJumpsDP(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;

        // dp[i] 表示到达位置 i 的最少跳跃次数
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 从 j 能否跳到 i
                if (j + nums[j] >= i && dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }

    /**
     * 贪心算法求解最少跳跃次数 O(n)
     * @param nums 每个位置的最大跳跃步数
     * @return 最少跳跃次数
     */
    public int minJumpsGreedy(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 <= i) {
                    return -1;
                }
            }
        }

        return jumps;
    }

    /**
     * 判断是否能到达终点
     * @param nums 每个位置的最大跳跃步数
     * @return 是否可达
     */
    public boolean canJump(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;
    }

    /**
     * 二维网格跳皮筋：从左上角到右下角的最短路径
     * grid[i][j] 表示在该位置最多可以向上下左右各跳多少格
     */
    public int minJumps2D(int[][] grid) {
        int rows = grid.length;
        if (rows == 0) return -1;
        int cols = grid[0].length;
        if (cols == 0) return -1;

        // BFS 求最短路径
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 0}); // {row, col, steps}
        visited[0][0] = true;

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], steps = curr[2];

            if (r == rows - 1 && c == cols - 1) {
                return steps;
            }

            int maxStep = grid[r][c];
            for (int[] dir : directions) {
                // 向该方向尝试跳跃 1 到 maxStep 格
                for (int step = 1; step <= maxStep; step++) {
                    int nr = r + dir[0] * step;
                    int nc = c + dir[1] * step;

                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) break;
                    if (visited[nr][nc]) continue;

                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, steps + 1});
                }
            }
        }

        return -1; // 无法到达
    }

    /**
     * 带障碍物的跳跃游戏（0表示障碍物，正数表示最大跳跃步数）
     */
    public int minJumpsWithObstacles(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;
        if (nums[0] == 0) return -1;

        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;

        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == 0) continue; // 障碍物无法起跳

            farthest = Math.max(farthest, i + nums[i]);

            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                if (currentEnd <= i) return -1;
            }
        }

        return jumps;
    }

    /**
     * 打印跳跃路径（回溯还原）
     */
    public List<Integer> getJumpPath(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] from = new int[n]; // 记录从哪个位置跳来
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        from[0] = -1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i && dp[j] != Integer.MAX_VALUE) {
                    if (dp[j] + 1 < dp[i]) {
                        dp[i] = dp[j] + 1;
                        from[i] = j;
                    }
                }
            }
        }

        // 回溯路径
        List<Integer> path = new ArrayList<>();
        if (dp[n - 1] == Integer.MAX_VALUE) return path;

        int cur = n - 1;
        while (cur != -1) {
            path.add(cur);
            cur = from[cur];
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        JumpRope solver = new JumpRope();

        // 测试1：一维最少跳跃
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println("=== 一维跳跃游戏 ===");
        System.out.println("数组: " + Arrays.toString(nums));
        System.out.println("是否可达: " + solver.canJump(nums));
        System.out.println("最少跳跃(DP): " + solver.minJumpsDP(nums));
        System.out.println("最少跳跃(贪心): " + solver.minJumpsGreedy(nums));
        System.out.println("跳跃路径: " + solver.getJumpPath(nums));

        // 测试2：二维网格
        System.out.println("\n=== 二维网格跳皮筋 ===");
        int[][] grid = {
            {2, 1, 1},
            {1, 1, 1},
            {1, 1, 0}
        };
        System.out.println("最少步数: " + solver.minJumps2D(grid));
    }
}

复杂度分析

贪心算法的核心洞察在于：不必关心具体从哪个位置起跳，只需维护当前跳数和下一步能到达的最远位置。这种”全局最优 = 局部最优”的性质是贪心策略生效的关键。

扩展思考

• 带权跳跃：不同跳跃消耗不同体力，使用 Dijkstra 算法求最小消耗路径。
• 双向跳跃：允许向前和向后跳跃，问题转化为无向图的最短路径。
• 多人博弈：多位玩家在网格上竞争到达终点，引入博弈论中的 minimax 策略。
• 随机跳跃：每次跳跃步数在 [1, nums[i]] 范围内随机，计算期望跳跃次数。