每日算法 — 使用java实现接金币：单调队列优化滑动窗口与动态规划路径决策

接金币是经典的街机小游戏，玩家控制角色在底部移动，接住从屏幕上方不断下落的金币。看似简单的操作背后，隐藏着动态规划最优路径与单调队列优化滑动窗口两大算法核心。当玩家每次只能移动有限距离时，如何规划移动路线以获得最高分数？本文将用Java完整实现接金币游戏的AI决策引擎，并深入讲解如何用单调队列将O(n·k)的DP优化到O(n)。

一、问题建模与游戏规则

1.1 为什么需要动态规划

假设屏幕被划分为 m 列，游戏持续 n 个时间单位。在每个时间点，部分列会掉落金币。玩家每次只能向左或向右移动最多 k 列。如果玩家直接采用”哪里有金币就往哪跑”的贪心策略，可能会因为移动距离限制而错过后续更密集的金币雨。因此需要全局最优的动态规划来决策每一步移动。

1.2 游戏状态定义

/**
 * 游戏配置常量
 */
class GameConfig {
    // 屏幕列数
    static final int COLS = 7;
    // 游戏总时长（时间单位数）
    static final int TIME_STEPS = 100;
    // 每步最大移动列数（滑动窗口半径）
    static final int MAX_MOVE = 2;
    // 金币分值
    static final int COIN_VALUE = 10;
}

/**
 * 单枚金币
 */
class Coin {
    // 所在列（0-based）
    int col;
    // 下落时间点
    int time;
    // 分值
    int value;

    Coin(int col, int time, int value) {
        this.col = col;
        this.time = time;
        this.value = value;
    }
}

/**
 * 玩家状态
 */
class Player {
    // 当前所在列
    int col;
    // 当前累计得分
    int score;

    Player(int col) {
        this.col = col;
        this.score = 0;
    }
}

1.3 游戏地图构建

将金币按时间分层存储，便于DP过程中快速查询某一时刻某列是否有金币。

import java.util.*;

/**
 * 游戏世界
 * 负责管理金币分布与玩家交互
 */
class GameWorld {
    // coinsAtTime[t][c] = 时间t、列c处的金币分值（0表示无金币）
    private final int[][] coinsAtTime;
    private final int timeSteps;
    private final int cols;

    GameWorld(int timeSteps, int cols) {
        this.timeSteps = timeSteps;
        this.cols = cols;
        this.coinsAtTime = new int[timeSteps][cols];
    }

    /**
     * 添加一枚金币到地图
     */
    void addCoin(Coin coin) {
        if (coin.time >= 0 && coin.time < timeSteps
                && coin.col >= 0 && coin.col < cols) {
            coinsAtTime[coin.time][coin.col] += coin.value;
        }
    }

    /**
     * 获取指定时间和列的金币分值
     */
    int getCoinValue(int time, int col) {
        if (time < 0 || time >= timeSteps || col < 0 || col >= cols) {
            return 0;
        }
        return coinsAtTime[time][col];
    }

    /**
     * 获取某一时刻所有列的金币分布
     */
    int[] getRow(int time) {
        if (time < 0 || time >= timeSteps) {
            return new int[cols];
        }
        return coinsAtTime[time].clone();
    }

    int getTimeSteps() { return timeSteps; }
    int getCols() { return cols; }
}

二、基础动态规划解法

2.1 状态转移方程

设 dp[t][c] 表示在第 t 个时间单位结束时，玩家位于第 c 列所能获得的最大分数。

状态转移：

dp[t][c] = coin[t][c] + max{ dp[t-1][c'] }
           其中 c' 满足 |c - c'| <= MAX_MOVE

即：当前得分 = 当前位置接到的金币 + 上一时刻在可达范围内的最大得分。

2.2 朴素DP实现

/**
 * 基础动态规划求解器
 * 时间复杂度：O(TIME_STEPS * COLS * (2*MAX_MOVE+1))
 * 空间复杂度：O(COLS) —— 使用滚动数组优化
 */
class BasicDPSolver {

    /**
     * 求解最优得分与路径
     * @param world 游戏世界
     * @param startCol 玩家起始列
     * @return 最优路径上每个时间点的列位置
     */
    int[] solve(GameWorld world, int startCol) {
        int T = world.getTimeSteps();
        int C = world.getCols();
        int K = GameConfig.MAX_MOVE;

        // 滚动数组：只保留上一时刻的dp值
        int[] prevDp = new int[C];
        int[] currDp = new int[C];
        // 记录路径：path[t][c] 表示到达(t,c)的最优前一列
        int[][] path = new int[T][C];

        // 初始化：第0时刻，玩家从startCol出发
        Arrays.fill(prevDp, Integer.MIN_VALUE / 2);
        if (startCol >= 0 && startCol < C) {
            prevDp[startCol] = world.getCoinValue(0, startCol);
        }

        // 逐时刻DP
        for (int t = 1; t < T; t++) {
            Arrays.fill(currDp, Integer.MIN_VALUE / 2);

            for (int c = 0; c < C; c++) {
                int bestPrevCol = -1;
                int bestPrevScore = Integer.MIN_VALUE / 2;

                // 枚举上一时刻所有可达的列
                int left = Math.max(0, c - K);
                int right = Math.min(C - 1, c + K);

                for (int pc = left; pc <= right; pc++) {
                    if (prevDp[pc] > bestPrevScore) {
                        bestPrevScore = prevDp[pc];
                        bestPrevCol = pc;
                    }
                }

                if (bestPrevCol != -1) {
                    currDp[c] = bestPrevScore + world.getCoinValue(t, c);
                    path[t][c] = bestPrevCol;
                }
            }

            // 滚动数组交换
            int[] temp = prevDp;
            prevDp = currDp;
            currDp = temp;
        }

        // 回溯找出最优路径
        return backtrackPath(path, prevDp, T, C);
    }

    /**
     * 回溯最优路径
     */
    private int[] backtrackPath(int[][] path, int[] lastDp, int T, int C) {
        int[] result = new int[T];

        // 找最终得分最大的列
        int bestCol = 0;
        for (int c = 1; c < C; c++) {
            if (lastDp[c] > lastDp[bestCol]) {
                bestCol = c;
            }
        }

        result[T - 1] = bestCol;
        // 从后向前回溯
        for (int t = T - 1; t > 0; t--) {
            result[t - 1] = path[t][result[t]];
        }

        return result;
    }
}

2.3 复杂度分析

当 K 较大时（例如玩家可以一次横跨大半屏幕），O(T × C × K) 的复杂度会成为瓶颈。

三、单调队列优化滑动窗口

3.1 优化思想

观察状态转移方程：

dp[t][c] = coin[t][c] + max{ dp[t-1][c'] }  (c-K <= c' <= c+K)

对于固定的时刻 t，我们需要对 prevDp 数组的每个位置 c，查询以 c 为中心、半径为 K 的滑动窗口最大值。这是一个经典的滑动窗口最值问题，可以用单调队列在 O(C) 时间内完成。

3.2 单调队列原理

单调队列维护一个双端队列，其中元素对应的 prevDp 值单调递减。对于每个位置 c：
1. 队尾维护：新元素入队时，从队尾弹出所有值小于等于新元素的索引，保证队列单调递减。
2. 队首维护：队首元素若已超出当前窗口范围 [c-K, c+K]，则从队首弹出。
3. 查询：队首即为当前窗口最大值。

3.3 优化后的DP实现

/**
 * 单调队列优化的动态规划求解器
 * 时间复杂度：O(TIME_STEPS * COLS)
 * 空间复杂度：O(COLS)
 */
class MonotonicQueueSolver {

    /**
     * 使用单调队列优化求解
     */
    int[] solve(GameWorld world, int startCol) {
        int T = world.getTimeSteps();
        int C = world.getCols();
        int K = GameConfig.MAX_MOVE;

        int[] prevDp = new int[C];
        int[] currDp = new int[C];
        int[][] path = new int[T][C];

        // 初始化
        Arrays.fill(prevDp, Integer.MIN_VALUE / 2);
        if (startCol >= 0 && startCol < C) {
            prevDp[startCol] = world.getCoinValue(0, startCol);
        }

        // 辅助数组：记录每个dp值来自哪个前驱列
        // 为了配合单调队列，我们在队列中存储(prevDp值, 列索引)的二元组
        for (int t = 1; t < T; t++) {
            Arrays.fill(currDp, Integer.MIN_VALUE / 2);

            // 使用单调队列处理当前时刻的所有列
            // 对于每个目标列c，可到达的前一列范围是 [c-K, c+K]
            // 等价于：对每个c，查询 prevDp 在区间 [c-K, c+K] 的最大值

            // 方法：将问题转换为"对每个c，窗口为 [c-K, c+K] 的滑动窗口最大值"
            // 这等价于从c=0到c=C-1扫描，窗口左边界 left = c-K，右边界 right = c+K
            // 我们使用一个从左到右扫描的单调队列

            Deque<Integer> deque = new ArrayDeque<>(); // 存储列索引，对应的prevDp值单调递减

            for (int c = 0; c < C; c++) {
                // 当前窗口的右边界为 c+K，左边界为 c-K
                // 当扫描到c时，需要确保队列中包含所有在 [c-K, c+K] 范围内的列
                // 等价地，我们让队列维护的范围随着c增大而右移

                // 将新进入窗口的元素 (c+K) 加入队列
                int newCol = c + K;
                if (newCol < C) {
                    // 队尾维护单调递减
                    while (!deque.isEmpty() && prevDp[deque.peekLast()] <= prevDp[newCol]) {
                        deque.pollLast();
                    }
                    deque.offerLast(newCol);
                }

                // 将离开窗口的元素 (c-K-1) 从队首移除
                int outCol = c - K - 1;
                if (outCol >= 0 && !deque.isEmpty() && deque.peekFirst() == outCol) {
                    deque.pollFirst();
                }

                // 此时队首就是窗口 [c-K, c+K] 内 prevDp 的最大值对应的列
                if (!deque.isEmpty()) {
                    int bestPrevCol = deque.peekFirst();
                    currDp[c] = prevDp[bestPrevCol] + world.getCoinValue(t, c);
                    path[t][c] = bestPrevCol;
                }
            }

            int[] temp = prevDp;
            prevDp = currDp;
            currDp = temp;
        }

        return backtrackPath(path, prevDp, T, C);
    }

    /**
     * 另一种更易理解的单调队列写法：
     * 对每个目标列c，直接求 max(prevDp[max(0,c-K)...min(C-1,c+K)])
     * 使用标准滑动窗口模板
     */
    int[] solveV2(GameWorld world, int startCol) {
        int T = world.getTimeSteps();
        int C = world.getCols();
        int K = GameConfig.MAX_MOVE;

        int[] prevDp = new int[C];
        int[] currDp = new int[C];
        int[][] path = new int[T][C];

        Arrays.fill(prevDp, Integer.MIN_VALUE / 2);
        if (startCol >= 0 && startCol < C) {
            prevDp[startCol] = world.getCoinValue(0, startCol);
        }

        for (int t = 1; t < T; t++) {
            // 使用单调队列求 prevDp 的每个滑动窗口最大值
            // 窗口大小为 2*K+1，但左右边界需要截断
            int[] windowMaxCol = slidingWindowMax(prevDp, C, K);

            for (int c = 0; c < C; c++) {
                int bestPrevCol = windowMaxCol[c];
                if (bestPrevCol >= 0) {
                    currDp[c] = prevDp[bestPrevCol] + world.getCoinValue(t, c);
                    path[t][c] = bestPrevCol;
                }
            }

            int[] temp = prevDp;
            prevDp = currDp;
            currDp = temp;
        }

        return backtrackPath(path, prevDp, T, C);
    }

    /**
     * 标准滑动窗口最大值：对每个位置c，返回窗口 [c-K, c+K] 内最大值的索引
     */
    private int[] slidingWindowMax(int[] arr, int n, int k) {
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 队首超出窗口范围则移除
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            // 队尾维护单调递减
            while (!deque.isEmpty() && arr[deque.peekLast()] <= arr[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 当窗口形成后（即 i >= 0 时都可以查询，因为左边界为 max(0, i-k)）
            // 但我们关心的是"以每个c为中心"的窗口，需要在另一侧也截断
            // 这里先记录以i为右端点的窗口最大值
            result[i] = deque.peekFirst();
        }

        // 上述结果 result[c] 对应窗口 [c-k, c] 的最大值索引
        // 我们需要的是 [c-k, c+k]，因此需要两次扫描（左右各一次）
        // 更简洁的方式：直接对每个c，取 left=c-k, right=c+k 的窗口最大值

        // 重新计算：使用前缀/后缀分解
        int[] leftMax = new int[n];  // leftMax[i] = arr在[i-k, i]范围内的最大值索引
        int[] rightMax = new int[n]; // rightMax[i] = arr在[i, i+k]范围内的最大值索引

        deque.clear();
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && arr[deque.peekLast()] <= arr[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            leftMax[i] = deque.peekFirst();
        }

        deque.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!deque.isEmpty() && deque.peekFirst() > i + k) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && arr[deque.peekLast()] <= arr[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            rightMax[i] = deque.peekFirst();
        }

        // 对于每个c，窗口 [c-k, c+k] = [c-k, c] ∪ [c, c+k]
        // 比较 leftMax[c] 和 rightMax[c] 对应的值
        for (int c = 0; c < n; c++) {
            int lIdx = leftMax[c];
            int rIdx = rightMax[c];
            // 确保索引在有效窗口内
            int leftBound = Math.max(0, c - k);
            int rightBound = Math.min(n - 1, c + k);

            if (lIdx < leftBound) lIdx = -1;
            if (rIdx > rightBound) rIdx = -1;

            if (lIdx == -1) {
                result[c] = rIdx;
            } else if (rIdx == -1) {
                result[c] = lIdx;
            } else {
                result[c] = (arr[lIdx] >= arr[rIdx]) ? lIdx : rIdx;
            }
        }

        return result;
    }

    private int[] backtrackPath(int[][] path, int[] lastDp, int T, int C) {
        int[] result = new int[T];
        int bestCol = 0;
        for (int c = 1; c < C; c++) {
            if (lastDp[c] > lastDp[bestCol]) {
                bestCol = c;
            }
        }
        result[T - 1] = bestCol;
        for (int t = T - 1; t > 0; t--) {
            result[t - 1] = path[t][result[t]];
        }
        return result;
    }
}

3.4 复杂度对比

当 K = 3 且 C = 7 时，两种方法差距不大。但当 K = 10 且 C = 50 时，单调队列优化的优势极为明显。

四、完整游戏模拟与可视化

/**
 * 接金币游戏主程序
 * 包含地图生成、AI决策执行与结果可视化
 */
public class CoinCollectorGame {

    public static void main(String[] args) {
        int cols = GameConfig.COLS;
        int timeSteps = GameConfig.TIME_STEPS;
        int maxMove = GameConfig.MAX_MOVE;

        // 构建随机游戏地图
        GameWorld world = generateRandomWorld(timeSteps, cols);

        System.out.println("=== 接金币游戏地图预览（前20步）===");
        printWorld(world, 20);

        int startCol = cols / 2; // 从中间列出发

        // 基础DP求解
        System.out.println("\n=== 基础DP求解 ===");
        long t1 = System.currentTimeMillis();
        BasicDPSolver basicSolver = new BasicDPSolver();
        int[] basicPath = basicSolver.solve(world, startCol);
        long t2 = System.currentTimeMillis();
        int basicScore = calculateScore(world, basicPath);
        System.out.println("基础DP得分: " + basicScore);
        System.out.println("基础DP耗时: " + (t2 - t1) + "ms");
        System.out.println("基础DP路径(前20步): " + Arrays.toString(Arrays.copyOf(basicPath, 20)));

        // 单调队列优化求解
        System.out.println("\n=== 单调队列优化DP求解 ===");
        long t3 = System.currentTimeMillis();
        MonotonicQueueSolver mqSolver = new MonotonicQueueSolver();
        int[] mqPath = mqSolver.solveV2(world, startCol);
        long t4 = System.currentTimeMillis();
        int mqScore = calculateScore(world, mqPath);
        System.out.println("单调队列DP得分: " + mqScore);
        System.out.println("单调队列DP耗时: " + (t4 - t3) + "ms");
        System.out.println("单调队列路径(前20步): " + Arrays.toString(Arrays.copyOf(mqPath, 20)));

        // 对比验证两种方法结果一致性
        System.out.println("\n=== 结果验证 ===");
        System.out.println("两种方法得分是否一致: " + (basicScore == mqScore));
        System.out.println("路径是否一致: " + Arrays.equals(basicPath, mqPath));

        // 执行可视化演示
        System.out.println("\n=== 游戏过程可视化（前20步）===");
        visualizeGame(world, mqPath, 20);
    }

    /**
     * 生成随机游戏地图
     * 每个时间点随机在1-3列生成金币
     */
    static GameWorld generateRandomWorld(int timeSteps, int cols) {
        GameWorld world = new GameWorld(timeSteps, cols);
        Random random = new Random(42); // 固定种子便于复现

        for (int t = 0; t < timeSteps; t++) {
            int coinCount = 1 + random.nextInt(3); // 每步1-3枚金币
            for (int i = 0; i < coinCount; i++) {
                int col = random.nextInt(cols);
                int value = GameConfig.COIN_VALUE;
                world.addCoin(new Coin(col, t, value));
            }
        }
        return world;
    }

    /**
     * 计算给定路径的总得分
     */
    static int calculateScore(GameWorld world, int[] path) {
        int score = 0;
        for (int t = 0; t < path.length; t++) {
            score += world.getCoinValue(t, path[t]);
        }
        return score;
    }

    /**
     * 打印游戏地图
     */
    static void printWorld(GameWorld world, int limit) {
        int cols = world.getCols();
        for (int t = 0; t < Math.min(limit, world.getTimeSteps()); t++) {
            int[] row = world.getRow(t);
            StringBuilder sb = new StringBuilder(String.format("t=%2d: ", t));
            for (int c = 0; c < cols; c++) {
                sb.append(row[c] > 0 ? "● " : "○ ");
            }
            System.out.println(sb);
        }
    }

    /**
     * 可视化游戏执行过程
     * ▲ 表示玩家所在位置
     */
    static void visualizeGame(GameWorld world, int[] path, int limit) {
        int cols = world.getCols();
        for (int t = 0; t < Math.min(limit, path.length); t++) {
            int[] row = world.getRow(t);
            int playerCol = path[t];
            StringBuilder sb = new StringBuilder(String.format("t=%2d: ", t));
            for (int c = 0; c < cols; c++) {
                if (c == playerCol) {
                    sb.append(row[c] > 0 ? "★ " : "▲ "); // 接到金币/空接
                } else {
                    sb.append(row[c] > 0 ? "● " : "  ");
                }
            }
            System.out.println(sb);
        }
    }
}

五、算法扩展与进阶思考

5.1 带权移动代价

如果移动到不同列需要消耗不同体力（例如距离越远消耗越大），状态转移变为：

dp[t][c] = coin[t][c] + max{ dp[t-1][c'] - cost(|c - c'|) }

此时单调队列的”滑动窗口最大值”变体仍适用，但需要将 cost 函数纳入考虑。当 cost 为凸函数时，可使用分治优化DP或Slope Trick进一步加速。

5.2 多玩家竞争场景

多个玩家争夺有限金币时，问题转化为博弈论中的资源抢占。每个玩家的最优策略不仅取决于地图，还取决于对手的位置预测。此时可引入 Minimax 或 蒙特卡洛树搜索 进行对抗决策。

5.3 在线学习与自适应难度

如果金币分布并非预先可知，而是动态生成，则可将问题建模为 Multi-Armed Bandit 或强化学习场景，让玩家通过历史数据学习金币出现的概率分布，动态调整站位策略。

六、总结

本文从接金币游戏出发，完整实现了两个版本的Java AI决策引擎：

• 基础动态规划：清晰的状态转移与滚动数组优化，时间复杂度 O(T·C·K)，适合理解问题本质。
• 单调队列优化：将滑动窗口最值查询降为 O(C)，总复杂度 O(T·C)，在 K 较大时效率提升显著。

核心算法价值不仅在于游戏本身，更在于单调队列优化DP这一技巧在大量竞赛与工程问题中的普适性：从股票买卖最大利润到字符串分割最小代价，滑动窗口最值无处不在。读者可在此基础上继续扩展：引入带权代价、多智能体博弈，或将单调队列与线段树结合处理更复杂的区间查询场景。