每日算法 — 使用java实现跳房子：动态规划最优跳跃路径与概率期望计算

游戏场景与算法概述

跳房子是一款经典儿童游戏，玩家投掷石子后按规则单脚跳跃拾取。本文将其抽象为算法问题：在一条由n个格子组成的道路上，每个格子有对应分数，玩家每次可跳1-3格，某些格子有奖励或惩罚。我们用Java实现动态规划求解最优跳跃路径，并计算不同策略的概率期望得分。

核心算法一：动态规划最优路径

假设一条道路有n个格子，每个格子有分数score[i]，玩家从起点出发，每次可跳跃1、2或3格，目标是到达终点时获得最高分。这是经典的DP问题。

import java.util.*;

public class HopscotchDP {
    // 动态规划求解最大得分路径
    public static Result findOptimalPath(int[] scores) {
        int n = scores.length;
        // dp[i]表示到达第i格能获得的最大分数
        int[] dp = new int[n];
        // path[i]记录到达第i格是从哪一格跳来的
        int[] path = new int[n];

        dp[0] = scores[0];
        path[0] = -1;

        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MIN_VALUE;
            // 尝试从前面1-3格跳过来
            for (int step = 1; step <= 3; step++) {
                int prev = i - step;
                if (prev >= 0 && dp[prev] + scores[i] > dp[i]) {
                    dp[i] = dp[prev] + scores[i];
                    path[i] = prev;
                }
            }
        }

        // 回溯重建路径
        List<Integer> route = new ArrayList<>();
        int cur = n - 1;
        while (cur != -1) {
            route.add(cur);
            cur = path[cur];
        }
        Collections.reverse(route);

        return new Result(dp[n - 1], route);
    }

    public static class Result {
        public int maxScore;
        public List<Integer> path;
        public Result(int score, List<Integer> path) {
            this.maxScore = score; this.path = path;
        }
        @Override
        public String toString() {
            return "MaxScore=" + maxScore + ", Path=" + path;
        }
    }

    public static void main(String[] args) {
        int[] scores = {0, 3, -1, 5, 2, -2, 8, 4, 1, 6};
        System.out.println(findOptimalPath(scores));
    }
}

核心算法二：带约束的进阶版本

在实际跳房子中，某些格子要求”单脚跳”（消耗体力，下一跳只能跳1格），某些格子是”安全区”（可以休息，恢复多格跳跃能力）。我们用状态机扩展DP。

public class AdvancedHopscotch {
    // 状态：0=正常，1=疲劳（只能跳1格）
    public static Result findPathWithConstraints(int[] scores, boolean[] singleLeg) {
        int n = scores.length;
        // dp[i][s]：到达第i格且状态为s时的最大分数
        int[][] dp = new int[n][2];
        int[][] path = new int[n][2];
        int[][] stateFrom = new int[n][2];

        for (int i = 0; i < n; i++) Arrays.fill(dp[i], Integer.MIN_VALUE);
        dp[0][0] = scores[0];

        for (int i = 0; i < n; i++) {
            for (int s = 0; s < 2; s++) {
                if (dp[i][s] == Integer.MIN_VALUE) continue;
                int maxStep = (s == 1) ? 1 : 3;
                for (int step = 1; step <= maxStep; step++) {
                    int next = i + step;
                    if (next >= n) continue;
                    int nextState = singleLeg[next] ? 1 : 0;
                    int newScore = dp[i][s] + scores[next];
                    if (newScore > dp[next][nextState]) {
                        dp[next][nextState] = newScore;
                        path[next][nextState] = i;
                        stateFrom[next][nextState] = s;
                    }
                }
            }
        }

        int bestState = dp[n-1][0] > dp[n-1][1] ? 0 : 1;
        return new Result(dp[n-1][bestState], reconstruct(path, stateFrom, n - 1, bestState));
    }

    private static List<Integer> reconstruct(int[][] path, int[][] state, int end, int s) {
        List<Integer> route = new ArrayList<>();
        int cur = end, curState = s;
        while (cur != 0 || curState != 0) {
            if (cur == 0 && curState == 0) break;
            route.add(cur);
            int prev = path[cur][curState];
            curState = state[cur][curState];
            cur = prev;
        }
        route.add(0);
        Collections.reverse(route);
        return route;
    }

    public static class Result {
        public int maxScore;
        public List<Integer> path;
        public Result(int score, List<Integer> path) { this.maxScore = score; this.path = path; }
    }
}

核心算法三：概率期望计算

如果某些格子的得分是随机的（比如投掷骰子决定加分），我们需要计算期望得分。假设每格有概率p获得奖励bonus[i]，否则得0。

public class ExpectedValueCalculator {
    // 计算期望得分的动态规划
    public static double calculateExpectedScore(double[] probs, int[] bonuses) {
        int n = probs.length;
        double[] exp = new double[n];
        exp[0] = probs[0] * bonuses[0];

        for (int i = 1; i < n; i++) {
            double bestPrev = Double.NEGATIVE_INFINITY;
            for (int step = 1; step <= 3; step++) {
                if (i - step >= 0) bestPrev = Math.max(bestPrev, exp[i - step]);
            }
            exp[i] = bestPrev + probs[i] * bonuses[i];
        }
        return exp[n - 1];
    }

    // 蒙特卡洛模拟验证期望
    public static double monteCarloSimulation(double[] probs, int[] bonuses, int trials) {
        Random rand = new Random();
        double total = 0;
        for (int t = 0; t < trials; t++) {
            int[] actual = new int[bonuses.length];
            for (int i = 0; i < probs.length; i++) {
                actual[i] = rand.nextDouble() < probs[i] ? bonuses[i] : 0;
            }
            total += HopscotchDP.findOptimalPath(actual).maxScore;
        }
        return total / trials;
    }
}

复杂度分析

总结

本文将跳房子游戏抽象为路径优化问题，通过动态规划高效求解最优跳跃策略，并引入概率期望处理随机得分场景。读者可将此框架扩展到更复杂的棋盘游戏，深入理解状态DP与期望计算的核心思想。