每日算法 — 使用java实现跑酷：动态规划与障碍物规避最优路径

引言

跑酷（Parkour）是一项在城市环境中快速穿越障碍物的运动。在算法视角下，跑酷可以抽象为一个二维网格上的路径规划问题：玩家从起点出发，需要跨越一系列障碍物，以最小的代价（时间或体力）到达终点。本文将使用Java实现一个跑酷路径规划系统，核心采用动态规划算法求解最优跳跃序列，并分析其时间复杂度与空间优化策略。

问题建模

将跑酷场景抽象为一条一维跑道，跑道上有若干个障碍物，每个障碍物具有不同的高度。玩家每次跳跃可以越过连续的一段障碍物，跳跃的代价与障碍物高度的最大值成正比。目标是找到从起点到终点的最小代价跳跃路径。

形式化描述：给定数组 heights[0..n-1] 表示每个位置障碍物的高度，玩家每次最多连续跨越 k 个位置，代价为这段区间内最大高度。求从位置 0 到达位置 n 的最小总代价。

算法设计：动态规划

设 dp[i] 为到达位置 i 的最小代价。状态转移方程为：

dp[i] = min(dp[j] + max(heights[j..i-1])) for all j in [max(0, i-k) .. i-1]

其中 max(heights[j..i-1]) 表示从位置 j 跳跃到位置 i 所跨越区间的最大高度。

单调队列优化

上述DP的时间复杂度为 O(n*k)。我们可以使用单调队列将复杂度优化到 O(n)。关键在于维护一个滑动窗口内的最大值，这正是单调递减队列的经典应用场景。

Java实现

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 跑酷路径规划：动态规划 + 单调队列优化
 * 问题：在跑道上跨越障碍物，每次最多跨k个位置，代价为区间内最大高度
 */
public class ParkourPathPlanner {

    /**
     * 基础动态规划解法，时间复杂度 O(n*k)
     */
    public static int minCostBasic(int[] heights, int k) {
        int n = heights.length;
        // dp[i] 表示到达位置i的最小代价（位置i表示第i个障碍物之后）
        int[] dp = new int[n + 1];
        dp[0] = 0; // 起点代价为0

        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            int maxHeight = 0;
            // 枚举上一次起跳的位置j
            for (int j = i - 1; j >= Math.max(0, i - k); j--) {
                maxHeight = Math.max(maxHeight, heights[j]);
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + maxHeight);
                }
            }
        }
        return dp[n];
    }

    /**
     * 单调队列优化版本，时间复杂度 O(n)
     * 使用单调递减队列维护滑动窗口最大值
     */
    public static int minCostOptimized(int[] heights, int k) {
        int n = heights.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;

        // 单调递减队列，存储下标，对应高度递减
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 1; i <= n; i++) {
            // 当前新加入窗口的元素是 heights[i-1]
            int currentHeight = (i - 1 < n) ? heights[i - 1] : 0;

            // 维护单调递减：移除队尾小于等于当前高度的元素
            while (!deque.isEmpty() && heights[deque.peekLast()] <= currentHeight) {
                deque.pollLast();
            }
            deque.offerLast(i - 1);

            // 移除超出窗口范围的元素（窗口大小为k，即j的范围是[i-k, i-1]）
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }

            // 此时队首就是窗口内的最大高度对应的下标
            int maxHeight = heights[deque.peekFirst()];

            // 简化版：仍需要枚举j来确定dp[j]的最小值
            // 实际上可以将dp值也纳入单调队列优化，这里展示一个平衡方案
            dp[i] = Integer.MAX_VALUE;
            for (int j = Math.max(0, i - k); j < i; j++) {
                maxHeight = Math.max(maxHeight, heights[j]);
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + getMaxInRange(heights, j, i - 1));
                }
            }
        }
        return dp[n];
    }

    private static int getMaxInRange(int[] arr, int left, int right) {
        int max = arr[left];
        for (int i = left + 1; i <= right; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    /**
     * 使用稀疏表（Sparse Table）进行RMQ查询，预处理O(nlogn)，查询O(1)
     * 整体DP复杂度优化为 O(n*k) -> O(n*k) 查询优化后接近 O(n)
     */
    static class SparseTable {
        int[][] st;
        int[] log;

        SparseTable(int[] arr) {
            int n = arr.length;
            log = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                log[i] = log[i / 2] + 1;
            }
            int k = log[n] + 1;
            st = new int[n][k];
            for (int i = 0; i < n; i++) {
                st[i][0] = arr[i];
            }
            for (int j = 1; j < k; j++) {
                for (int i = 0; i + (1 << j) <= n; i++) {
                    st[i][j] = Math.max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
                }
            }
        }

        int query(int l, int r) {
            int j = log[r - l + 1];
            return Math.max(st[l][j], st[r - (1 << j) + 1][j]);
        }
    }

    /**
     * 使用稀疏表优化的完整DP解法
     */
    public static int minCostSparseTable(int[] heights, int k) {
        int n = heights.length;
        SparseTable st = new SparseTable(heights);
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = Math.max(0, i - k); j < i; j++) {
                int maxH = st.query(j, i - 1);
                dp[i] = Math.min(dp[i], dp[j] + maxH);
            }
        }
        return dp[n];
    }

    /**
     * 空间优化版本：使用滚动数组，空间复杂度 O(k)
     */
    public static int minCostSpaceOptimized(int[] heights, int k) {
        int n = heights.length;
        // 只保留最近k个位置的dp值
        int[] dp = new int[k + 1];

        for (int i = 1; i <= n; i++) {
            int currentMin = Integer.MAX_VALUE;
            int maxHeight = 0;
            for (int step = 1; step <= k && i - step >= 0; step++) {
                int idx = (i - step) % (k + 1);
                maxHeight = Math.max(maxHeight, heights[i - step]);
                if (dp[idx] != Integer.MAX_VALUE) {
                    currentMin = Math.min(currentMin, dp[idx] + maxHeight);
                }
            }
            dp[i % (k + 1)] = currentMin;
        }
        return dp[n % (k + 1)];
    }

    public static void main(String[] args) {
        int[] heights = {2, 3, 1, 4, 2, 5, 3, 2};
        int k = 3;

        System.out.println("=== 跑酷路径规划 ===");
        System.out.println("障碍物高度: " + java.util.Arrays.toString(heights));
        System.out.println("最大跳跃距离: " + k);
        System.out.println();

        int cost1 = minCostBasic(heights, k);
        System.out.println("基础DP最小代价: " + cost1);

        int cost2 = minCostSparseTable(heights, k);
        System.out.println("稀疏表优化最小代价: " + cost2);

        int cost3 = minCostSpaceOptimized(heights, k);
        System.out.println("空间优化最小代价: " + cost3);
    }
}

二维跑酷扩展

将场景扩展到二维平面，障碍物以坐标形式分布，玩家需要从左边界移动到右边界，每次可以向右上方、正右方或右下方移动一格。

/**
 * 二维跑酷：网格上的最小代价路径
 */
public class Parkour2D {

    public static int minCost2D(int[][] grid, int rows, int cols) {
        // dp[i][j] 表示到达 (i,j) 的最小代价
        int[][] dp = new int[rows][cols];

        // 初始化第一列
        for (int i = 0; i < rows; i++) {
            dp[i][0] = grid[i][0];
        }

        // 逐列填充
        for (int j = 1; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                dp[i][j] = dp[i][j - 1] + grid[i][j]; // 从正左方来
                if (i > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + grid[i][j]); // 从左上方
                }
                if (i < rows - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1] + grid[i][j]); // 从左下方
                }
            }
        }

        // 返回最后一列的最小值
        int result = dp[0][cols - 1];
        for (int i = 1; i < rows; i++) {
            result = Math.min(result, dp[i][cols - 1]);
        }
        return result;
    }
}

复杂度分析

其中 n 为障碍物数量，k 为最大跳跃距离。

总结

本文通过跑酷游戏场景，讲解了动态规划在路径规划问题中的应用。从基础DP出发，逐步引入稀疏表进行RMQ优化，最后通过滚动数组压缩空间。读者可以掌握区间最值查询与动态规划的结合技巧，并将其迁移到类似的最优路径问题中。