每日算法 — 使用java实现跳房子游戏：动态规划与最优跳跃路径

跳房子（Hopscotch）是流传于世界各地的童年经典游戏。玩家在画有数字方格的地面上一路跳跃，规则简单却蕴含丰富的决策空间。本文用Java实现一个智能跳房子游戏，核心在于通过动态规划计算从起点到终点的最优跳跃路径，并分析不同格子奖励权重下的策略选择。

游戏规则与问题建模

标准跳房子场地由一排编号方格组成，每个格子标有数字代表到达该格可获得的分数。玩家从起点出发，每次可跳1格或2格，目标是到达终点时累计得分最高。

将问题抽象为：给定长度为n的数组scores[]，从第0格出发，每次前进1或2步，求到达第n-1格时的最大累计得分。

动态规划核心思路

设dp[i]表示到达第i格时的最大累计得分。状态转移方程为：

dp[i] = scores[i] + max(dp[i-1], dp[i-2])

初始条件：dp[0] = scores[0]，dp[1] = scores[0] + scores[1]。最终结果存储于dp[n-1]。

该问题与”爬楼梯”问题同构，但增加了格子权重，使贪心策略不再适用，必须用动态规划保证全局最优。

Java完整实现

import java.util.*;

/**
 * 跳房子游戏 - 动态规划最优路径求解
 * 核心问题：从起点到终点，每次跳1或2格，求最大累计得分
 */
public class HopscotchGame {

    // ==================== 核心算法：动态规划 ====================

    /**
     * 计算到达终点的最大累计得分
     * @param scores 每个格子的分数数组
     * @return 最大累计得分
     */
    public static int maxScore(int[] scores) {
        if (scores == null || scores.length == 0) return 0;
        if (scores.length == 1) return scores[0];

        // dp[i] 表示到达第i格的最大累计得分
        int n = scores.length;
        int[] dp = new int[n];

        dp[0] = scores[0];
        dp[1] = scores[0] + scores[1];

        for (int i = 2; i < n; i++) {
            // 从i-1跳1步 或 从i-2跳2步，取较大值加上当前格分数
            dp[i] = scores[i] + Math.max(dp[i - 1], dp[i - 2]);
        }

        return dp[n - 1];
    }

    /**
     * 空间优化版本：仅使用O(1)额外空间
     * 观察到dp[i]只依赖前两个状态，可用滚动变量替代数组
     */
    public static int maxScoreOptimized(int[] scores) {
        if (scores == null || scores.length == 0) return 0;
        if (scores.length == 1) return scores[0];

        int prev2 = scores[0];        // dp[i-2]
        int prev1 = scores[0] + scores[1]; // dp[i-1]

        for (int i = 2; i < scores.length; i++) {
            int curr = scores[i] + Math.max(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }

    /**
     * 重构最优路径：不仅求最大得分，还要输出具体跳法
     * @return 按顺序访问的格子索引列表
     */
    public static List<Integer> getOptimalPath(int[] scores) {
        int n = scores.length;
        if (n == 0) return Collections.emptyList();

        int[] dp = new int[n];
        int[] choice = new int[n]; // 记录从哪个位置跳来：1表示i-1, 2表示i-2

        dp[0] = scores[0];
        if (n > 1) {
            dp[1] = scores[0] + scores[1];
            choice[1] = 1;
        }

        for (int i = 2; i < n; i++) {
            if (dp[i - 1] >= dp[i - 2]) {
                dp[i] = scores[i] + dp[i - 1];
                choice[i] = 1;
            } else {
                dp[i] = scores[i] + dp[i - 2];
                choice[i] = 2;
            }
        }

        // 回溯重构路径
        List<Integer> path = new ArrayList<>();
        int i = n - 1;
        while (i >= 0) {
            path.add(i);
            if (i == 0) break;
            i -= choice[i];
            if (i < 0) i = 0; // 安全处理
        }
        Collections.reverse(path);
        return path;
    }

    // ==================== 扩展：带限制条件变体 ====================

    /**
     * 变体1：某些格子为"陷阱"不能踩，求最大得分路径
     * @param scores 分数数组
     * @param traps  true表示该格为陷阱不能踩
     */
    public static int maxScoreWithTraps(int[] scores, boolean[] traps) {
        int n = scores.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);

        if (!traps[0]) dp[0] = scores[0];
        if (n > 1 && !traps[1] && dp[0] != Integer.MIN_VALUE) {
            dp[1] = dp[0] + scores[1];
        }

        for (int i = 2; i < n; i++) {
            if (traps[i]) continue; // 陷阱格跳过
            int bestPrev = Integer.MIN_VALUE;
            if (dp[i - 1] != Integer.MIN_VALUE) bestPrev = Math.max(bestPrev, dp[i - 1]);
            if (dp[i - 2] != Integer.MIN_VALUE) bestPrev = Math.max(bestPrev, dp[i - 2]);
            if (bestPrev != Integer.MIN_VALUE) {
                dp[i] = scores[i] + bestPrev;
            }
        }

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

    /**
     * 变体2：可跳1/2/3格的三阶动态规划
     */
    public static int maxScoreThreeSteps(int[] scores) {
        int n = scores.length;
        if (n == 0) return 0;
        if (n == 1) return scores[0];
        if (n == 2) return scores[0] + scores[1];

        int[] dp = new int[n];
        dp[0] = scores[0];
        dp[1] = scores[0] + scores[1];
        dp[2] = scores[2] + Math.max(dp[1], Math.max(dp[0], scores[0]));

        for (int i = 3; i < n; i++) {
            dp[i] = scores[i] + Math.max(dp[i - 1], Math.max(dp[i - 2], dp[i - 3]));
        }
        return dp[n - 1];
    }

    // ==================== 主程序与演示 ====================

    public static void main(String[] args) {
        // 示例场地：10个格子，分数各不相同
        int[] scores = {2, 7, 9, 3, 1, 5, 8, 4, 6, 10};

        System.out.println("========== 跳房子游戏 - 动态规划求解 ==========");
        System.out.println("场地分数: " + Arrays.toString(scores));
        System.out.println();

        // 基础DP求解
        int maxScore = maxScore(scores);
        System.out.println("最大累计得分: " + maxScore);

        // 空间优化版本
        int maxScoreOpt = maxScoreOptimized(scores);
        System.out.println("空间优化版本得分: " + maxScoreOpt);

        // 重构最优路径
        List<Integer> path = getOptimalPath(scores);
        System.out.println("最优路径 (格子索引): " + path);
        System.out.print("路径得分明细: ");
        int sum = 0;
        for (int idx : path) {
            System.out.print(scores[idx] + " ");
            sum += scores[idx];
        }
        System.out.println("= " + sum);

        // 陷阱变体演示
        System.out.println("\n========== 陷阱变体 ==========");
        boolean[] traps = {false, false, true, false, false, true, false, false, false, false};
        int trapScore = maxScoreWithTraps(scores, traps);
        System.out.println("避开陷阱后的最大得分: " + trapScore);

        // 三阶跳跃变体
        System.out.println("\n========== 三阶跳跃变体 ==========");
        int threeScore = maxScoreThreeSteps(scores);
        System.out.println("可跳1/2/3格的最大得分: " + threeScore);
    }
}

算法复杂度分析

状态转移每次仅需常数时间比较与加法，故总时间为线性。空间优化版本利用滚动变量，将存储开销降至常数级别，适合处理超长场地。

扩展思考

1. K步跳跃：若允许跳1至k格，状态转移扩展为dp[i] = scores[i] + max(dp[i-1], ..., dp[i-k])，可用单调队列优化至O(n)。
2. 多玩家博弈：引入两名玩家轮流跳跃，格子被踩后分数清零，转化为组合博弈问题，可用Sprague-Grundy定理分析。
3. 概率权重：若每次跳跃有概率落入”双倍奖励格”，则期望值计算需引入概率DP模型。

跳房子看似简单的童年游戏，其最优路径问题却是动态规划的经典入门案例。掌握状态定义与转移方程的构建方法，是攻克更复杂DP问题的基石。