博弈 DP

动态规划 ⭐⭐⭐ 进阶 🔥 中频

💡 核心要点

博弈 DP 的本质是 MinMax 思想：轮到我时取净收益最大的选择，轮到对手时对手同样最优——用 dp[i][j] 表示先手在区间 [i,j] 上的净收益（先手得分 − 后手得分），即可统一两个玩家的最优行为。

识别信号

两个玩家轮流操作，双方都采取最优策略（没有随机性）
题目问的是先手是否必赢，或先手与后手的最大得分差
关键词：博弈、轮流取、最优策略、先手必胜/后手必胜
典型场景：从数组两端轮流取数、Nim 取石子、棋盘类两人对弈

通用思考框架

MinMax 核心思想

轮到我（先手）时，我选择让自己净收益最大的操作；轮到对手时，对手同样最优，因此对手也会让他自己的净收益最大——这等价于让我的净收益最小。

将两个玩家的行为统一到一个量上，可以避免分别维护两个人的得分数组。

状态定义常见模式

模式一：净收益（推荐）

转移方程（以区间两端取数为例）：

解释：

取左端：接下来对手在上先手，对手的净收益是，所以我的净收益
取右端：类似地，我的净收益
我取两种情况中较大的那个

判断先手是否获胜：

模式二：分别定义先手/后手得分（适合某些变体）

两者满足：，因此净收益模式本质上等价。

区间 DP 遍历顺序

博弈 DP 通常是区间 DP，必须按区间长度从小到大枚举，确保计算时和已经就绪。

for (int len = 1; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        // 计算 dp[i][j]
    }
}

Sprague-Grundy 定理简介（Nim 游戏）

对于 Nim 游戏及一类组合游戏，有更直接的数学结论：

每个局面有一个 Grundy 值（也叫 nimber）
多个独立子游戏组合时，总 Grundy 值 $= $ 各子游戏 Grundy 值的异或
若总 Grundy 值，后手必赢；否则先手必赢

标准 Nim 游戏（多堆石子，每次从一堆取任意数量）：

这类题目直接用数学结论，不需要 DP。

典型例题：预测赢家 LeetCode 486

题目描述

给你一个整数数组 nums。玩家 1 和玩家 2 轮流从数组两端取数，取完后该数从数组中移除。两人都采取最优策略。若玩家 1 能获得大于等于玩家 2 的分数，返回 true，否则返回 false。

示例：

nums = [1, 5, 2] → false（玩家 2 必赢）
nums = [1, 5, 233, 7] → true（玩家 1 能赢）

五步法

第一步：定义状态

最终答案：dp[0][n-1] >= 0 时玩家 1 获胜。

第二步：状态转移

先手可以取左端或右端：

第三步：初始化

当时，区间只有一个元素，先手直接取走，净收益就是该元素本身：

第四步：遍历顺序

区间长度从 1 到，外层枚举长度，内层枚举起点。

第五步：提取答案

dp[0][n-1] >= 0

Java 代码

java

class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        // dp[i][j] = 在 nums[i..j] 中先手能获得的最大净收益
        int[][] dp = new int[n][n];

        // 初始化：区间长度为 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }

        // 按区间长度从小到大枚举
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                // 取左端 nums[i]：对手在 [i+1,j] 先手，净收益 dp[i+1][j]
                // 取右端 nums[j]：对手在 [i,j-1] 先手，净收益 dp[i][j-1]
                dp[i][j] = Math.max(
                    nums[i] - dp[i + 1][j],
                    nums[j] - dp[i][j - 1]
                );
            }
        }

        // 先手净收益 >= 0 说明玩家 1 得分 >= 玩家 2
        return dp[0][n - 1] >= 0;
    }
}

复杂度分析：

时间复杂度：，需要填满二维 DP 表
空间复杂度：，存储二维 DP 表（可用滚动数组优化至）

干跑验证

以 nums = [1, 5, 2] 为例：


1	-4	2
—	5	3
—	—	2

等等，重新算：
实际（先手取 5，净收益 4）

，返回 false，玩家 1 输，与预期一致。

前后手例题：石子游戏 III LeetCode 1406

上一题从两端取，本题从前端顺序取，且每次可取 1~3 堆，是"前后手轮流从头部拿"的经典模型，最终需要判断先手（Alice）与后手（Bob）谁的总分更高。

题目描述

有 n 堆石子排成一列，stoneValue[i] 为第 i 堆的价值（可为负）。Alice 先手、Bob 后手轮流从最前面取 1、2 或 3 堆。两人都最优。返回 "Alice"、"Bob" 或 "Tie"。

示例： stoneValue = [1, 2, 3, 7] → "Bob"（Alice 无论怎么取，Bob 都能赢）

五步法

第一步：定义状态

因为只从前端取，一维即可。用后缀净收益统一前后手：

第二步：状态转移

当前先手取前 k（k=1,2,3）堆，拿到这 k 堆之和 sum，随后对手在 stoneValue[i+k..] 上成为新的先手，其净收益是，故我的净收益是：

第三步：初始化

（没有石子，净收益为 0）。

第四步：遍历顺序

i 从 n-1 倒推到 0（因为依赖后面的）。

第五步：提取答案

→ Alice， → Bob， → Tie。

Java 代码

java

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        // dp[i] = 剩 stoneValue[i..n-1] 时先手的最大净收益
        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int sum = 0;
            dp[i] = Integer.MIN_VALUE;
            // 当前先手取前 k 堆（k = 1,2,3）
            for (int k = 1; k <= 3 && i + k <= n; k++) {
                sum += stoneValue[i + k - 1];
                // 取完这 k 堆，对手在 [i+k..] 先手，其净收益 dp[i+k]
                dp[i] = Math.max(dp[i], sum - dp[i + k]);
            }
        }

        if (dp[0] > 0) return "Alice";
        if (dp[0] < 0) return "Bob";
        return "Tie";
    }
}

复杂度分析：

时间复杂度：，每个状态最多枚举 3 种取法
空间复杂度：，可用 3 个滚动变量优化到

干跑验证

以 stoneValue = [1, 2, 3, 7]（）为例，：

	可取组合（sum − dp[i+k]）
3		7
2	，	5
1	，，	12
0	，，	-1

→ 返回 "Bob"，与预期一致。

🔑 前后手对比

两端取（486/877）：状态是二维区间 dp[i][j]，先手可选左右两端。
前端取（1406）：状态是一维后缀 dp[i]，先手只能从头连续取若干堆。
二者转移公式形态一致：我的净收益 = 我拿到的分 − 对手接手后的净收益，这正是前后手博弈 DP 的统一核心。

延伸题目

题目	链接	难度	关键思路
石子游戏	LC 877	中等	与 486 相同框架；数学上先手必赢（数组长度为偶数）
我能赢吗	LC 464	中等	状态压缩 + 博弈记忆化，`dp[mask]` 表示当前可用数字集合下先手是否必赢
Nim 游戏	LC 292	简单	纯数学结论：先手必赢，无需 DP
石子游戏 II	LC 1140	中等	`dp[i][m]` 表示从第 `i` 堆开始、当前 `M=m` 时先手的最大得分，加入后缀和优化
石子游戏 III	LC 1406	困难	`dp[i]` 表示从第 `i` 堆开始先手的最大净收益，每次可取 1~3 堆

常见陷阱与调试

陷阱一：混淆"先手得分"与"净收益"

如果用 dp[i][j] 表示先手的绝对得分（而非净收益），转移时需要同时维护后手得分，逻辑更繁琐且容易出错。推荐始终使用净收益定义，统一两个玩家的行为。

陷阱二：忽视对手也是最优策略

不能假设对手会犯错或随机选择。净收益公式中，取后对手得到的净收益，我的净收益是，这正是"对手最优"的体现。

陷阱三：区间 DP 遍历顺序错误

必须按区间长度从小到大枚举。若按左端点 i 从大到小枚举，则计算 dp[i][j] 时 dp[i][j-1] 可能还未计算（因为 j-1 > i 时 dp[i][j-1] 对应的左端点仍是 i，但长度更小，需先算）。

错误写法：

java

// 错误：按 i 从大到小，j 从小到大，遍历顺序不保证依赖已算
for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
        // dp[i][j-1] 可能已算，但 dp[i+1][j] 依赖 i+1 > i，此时已算 ✓
        // 实际上按 i 从大到小也可以，但初学者易混淆，推荐按长度枚举
    }
}

推荐写法（按长度枚举，语义最清晰）：

java

for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
    }
}

陷阱四：Nim 游戏误用 DP

LC 292（Nim 游戏）只有一堆石子，每次取 1~3 个，直接用判断，不需要也不应该写 DP。遇到 Nim 类题目，先判断是否有数学结论。

陷阱五：状压博弈忘记记忆化

LC 464（我能赢吗）的状态空间是，必须用 Map<Integer, Boolean> 或 Boolean[] 数组做记忆化，否则朴素递归会超时。

博弈 DP ​

识别信号 ​

通用思考框架 ​

MinMax 核心思想 ​

状态定义常见模式 ​

区间 DP 遍历顺序 ​

Sprague-Grundy 定理简介（Nim 游戏） ​

典型例题：预测赢家 LeetCode 486 ​

题目描述 ​

五步法 ​

Java 代码 ​

干跑验证 ​

前后手例题：石子游戏 III LeetCode 1406 ​

题目描述 ​

五步法 ​

Java 代码 ​

干跑验证 ​

延伸题目 ​

常见陷阱与调试 ​

博弈 DP

识别信号

通用思考框架

MinMax 核心思想

状态定义常见模式

区间 DP 遍历顺序

Sprague-Grundy 定理简介（Nim 游戏）

典型例题：预测赢家 LeetCode 486

题目描述

五步法

Java 代码

干跑验证

前后手例题：石子游戏 III LeetCode 1406

题目描述

五步法

Java 代码

干跑验证

延伸题目

常见陷阱与调试