博弈DP

字数统计: 4.7k字 | 阅读时长: 19分

2022-01-17

lc题目汇总64, leetcode424, 动态规划129, 博弈9, 搜索62

摘要: 本文介绍博弈 DP 的原理和例题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

博弈是应用数学的一个分支，表示在多决策主体之间行为具有相互作用时，各主体根据所掌握信息以及对自身能力的认知，做出有利于自己的决策的一种行为理论。这类问题通常没有那么直接，需要进行一定的推演才能发现问题本质。

博弈 DP 并不是一种特殊的动态规划类型，而是一种常见的应用场景。类似的还有计数DP，概率DP，等等。实际上在解决博弈DP问题时候，最终用的DP类型，根据对问题建模后状态之间的关系，可能是线性DP，树形DP，图上DP等等，与具体问题有关系。

博弈 DP 的理论基础主要是 minimax，公式如下：

$\min\limits_{x \in X^{(0)}}\max\limits_{1 \leq i \leq m}\{f_{i}(x)\}$

其中 $f_{i}(x)$ 是目标函数，$f(x) = \max\limits_{1 \leq j \leq m}f_{i}(x)$ 为极大值函数。

博弈DP中的状态转移方程一般是下面这样，dp[i] 的意思是在状态 i 先手方可以取得的最大收益，当然会根据问题的不同产生很多变化，比如会需要附加状态或状态压缩等等。

$dp[i] = \max\limits_{j\in adj(i)}(f[i][j] + \min\limits_{k\in adj(j)}dp[k])$

其中 f[i][j] 表示先手方在状态 i 选择走到状态 j 可获得的收益；adj(i) 表示可以从状态 i 到达的状态集合。整个状态转移方程与 minimax 的公式可以对上。

本文我们详细拆解 leetcode 中的一些题目，看看博弈DP中的基本套路。

(1) 877. 石子游戏 / 486. 预测赢家

minimiax + 区间DP

(2) 1908. Nim 游戏 II

minimax + 状态压缩DP

(3) 375. 猜数字大小 II

minimax + 区间DP

(4) 294. 翻转游戏 II

minimax + 记忆化搜索

877. 石子游戏 / 486. 预测赢家

这两道题完全一样，我们以 877 为例。

算法要点

minimax + 区间DP

题目描述

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有正整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

提示：
2 <= piles.length <= 500
piles.length 是 偶数
1 <= piles[i] <= 500
sum(piles[i]) 是 奇数

示例 1：
输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。
示例 2：
输入：piles = [3,7,2,3]
输出：true

算法

首先我们分析问题，有 Alice 和 Bob 两个人，他们需要轮流地分别做出决策：是取开始处的一堆还是取结束处的一堆。决策的依据是最有利于自己，也就是取自己最终可以拿到最多棋子的那一堆。而两个人的决策会相互作用，也就是 Alice 这一轮的决策会影响到 Bob 下一轮的决策。

可以发现这个问题完全吻合博弈问题的特点:

在多决策主体之间行为具有相互作用时，各主体根据所掌握信息以及对自身能力的认知，做出有利于自己的决策的一种行为。

该问题满足零和博弈：所有博弈方的利益之和为一个常数，这样一方有所得，其它方必然有损失。零和博弈的博弈各方是不合作的，最大化自己收益的过程就是最小化对方收益的过程。

对手总会为自己挑选最坏的结果，给自己留下可能收益中最小的，也就是可能损失最大的，因此决策的方向是最小化自己的最大损失，这种算法称为极小化极大算法或者 minimax 算法。

初始的一行石堆为 piles[0..n-1]，由 Alice 先选。我们考查 Alice 最多可以拿到多少石子，如果超过了总石子的一半，那么 Alice 获胜，返回 True，否则 Bob 获胜，返回 False。

Alice 在第一轮可以选择 piles[0] 或 piles[n-1]。无论选择哪个，下一轮 Bob 都会在留下的一行石子中做出 Alice 能获得最少石子的选择。具体如下：

如果选择了 piles[0]，Bob 就会在留下的 piles[1..n-1] 中做出自己能够获得最多石子(也就是 Alice 能够获得最少石子)的选择。
如果选择了 piles[n-1]，Bob 就会在留下的 piles[0..n-2] 中做出自己能够获得最多石子(也就是 Alice 能够获得最少石子)的选择。

基于以上分析，我们写出博弈 DP 算法，求出 Alice 先手最多可以取到的石子数

状态定义
dp[i][j] := 当前一行石堆为 piles[i..j]，Alice 先拿，最多可以获得多少

答案
dp[0][n - 1]

初始化
dp[i][i] = piles[i]
dp[i][i + 1] = max(piles[i], piles[i + 1])

状态转移
dp[i][j] = max(piles[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
              ,piles[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
              )

代码

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n));
        int all = 0;
        for(int i = 0; i < n; ++i)
        {
            all += piles[i];
            dp[i][i] = piles[i];
        }
        for(int i = 0; i < n - 1; ++i)
            dp[i][i + 1] = max(piles[i], piles[i + 1]);
        for(int l = 3; l <= n; ++l)
        {
            // l 为区间长度
            for(int i = 0; i + l <= n; ++i)
            {
                int j = i + l - 1;
                dp[i][j] = max(piles[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
                              ,piles[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
                              );
            }
        }
        return dp[0][n - 1] * 2 > all;
    }
};

1908. Nim 游戏 II

算法要点

minimax + 状态压缩DP

题目描述

Alice 和 Bob 交替进行一个游戏，由 Alice 先手。

在游戏中，共有 n 堆石头。在每个玩家的回合中，玩家需要选择任一非空石头堆，从中移除任意非零数量的石头。如果不能移除任意的石头，就输掉游戏，同时另一人获胜。

给定一个整数数组 piles ，piles[i] 为第 i 堆石头的数量，如果 Alice 能获胜返回 true ，反之返回 false 。

Alice 和 Bob 都会采取最优策略。

提示：
n == piles.length
1 <= n <= 7
1 <= piles[i] <= 7

示例 1：
输入：piles = [1]
输出：true
解释：只有一种可能的情况：

第一回合，Alice 移除了第 1 堆中 1 块石头。piles = [0]。

第二回合，Bob 没有任何石头可以移除。Alice 获胜。
示例 2：
输入：piles = [1,1]
输出：false
解释：可以证明，Bob一定能获胜。一种可能的情况：

第一回合，Alice 移除了第 1 堆中 1 块石头。 piles = [0,1]。

第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0]。

第三回合，Alice 没有任何石头可以移除。Bob 获胜。
示例 3：
输入：piles = [1,2,3]
输出：false
解释：可以证明，Bob一定能获胜。一种可能的情况：

第一回合，Alice 移除了第 3 堆中 3 块石头。 piles = [1,2,0]。

第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [1,1,0]。

第三回合，Alice 移除了第 1 堆中 1 块石头。piles = [0,1,0]。

第四回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0,0]。

第三回合，Alice 没有任何石头可以移除。Bob 获胜。

算法

初始时，石堆为 piles[0..n-1], 先手可以采取的动作为从任意一堆中拿走任意个。

如果拿第 i 堆，那么可以有拿 1, 2, …, piles[i]，这么多选择。因此总的选择个数为

$\sum\limits_{i=0}\limits^{n-1}piles[i]$

这些选择之后到达的状态都是有可能的新状态。

我们发现，想要表达这些状态，piles 中的每个位置的当前石子个数都需要单独表示。例如初始石堆为 [1, 3, 2], 那么下面这些都是可能的状态，

[1, 3, 2], [1, 3, 1], [1, 3, 0]
[1, 2, 2], [1, 2, 1], [1, 2, 0]
[1, 1, 2], [1, 1, 1], [1, 1, 0]
[1, 0, 2], [1, 0, 1], [1, 0, 0]
[0, 3, 2], [0, 3, 1], [0, 3, 0]
[0, 2, 2], [0, 2, 1], [0, 2, 0]
[0, 1, 2], [0, 1, 1], [0, 1, 0]
[0, 0, 2], [0, 0, 1], [0, 0, 0]

这样对于 piles，总状态个数为

$\prod\limits_{i=0}\limits^{n-1}(piles[i] + 1)$

由于 piles[i] 的范围是 [1, 7]，因此可以用 3 个二进制位表示 piles[i]。piles 的长度最长是 7，因此用 21 个二进制位就可以表示所有可能的状态。

基于以上分析，我们可以写出博弈 DP 算法

状态定义
dp[i] := 压缩后的状态为 i 时，先手最终的胜负

答案
dp[s], s 为 piles[0..n-1] 压缩后的状态

初始化
dp[0] = False

状态转移
dp[s] = !(dp[t1] && dp[t2] && ... && dp[tm])
t1, t2, ... tm 为先手在 s 执行一次操作后可到达的状态

代码

class Solution {
public:
    bool nimGame(vector<int>& piles) {
        int n = piles.size();
        vector<int> dp(1 << (n * 3), -1);
        dp[0] = 0;
        int t = 0;
        for(int i = 0; i < n; ++i)
            t += (piles[i] << (3 * i));
        return solve(t, n, dp) == 1;
    }

private:
    int solve(int s, const int n, vector<int>& dp)
    {
        if(dp[s] != -1)
            return dp[s];
        for(int i = 0; i < n; ++i)
        {
            int m = ((s >> (i * 3)) & 7);
            for(int j = 0; j < m; ++j)
            {
                int t = s & (~(7 << (i * 3)));
                t += j << (i * 3);
                if(solve(t, n, dp) == 0)
                    return dp[s] = 1;
            }
        }
        return dp[s] = 0;
    }
};

375. 猜数字大小 II

算法要点

minimax + 区间DP

题目描述

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字。
你来猜我选了哪个数字。
如果你猜到正确的数字，就会赢得游戏。
如果你猜错了，那么我会告诉你，我选的数字比你的更大或者更小，并且你需要继续猜数。
每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会输掉游戏。
给你一个特定的数字 n ，返回能够确保你获胜的最小现金数，不管我选择哪个数字。

1 2	提示： 1 <= n <= 200

示例 1：
输入：n = 10
输出：16
解释：制胜策略如下：

数字范围是 [1,10] 。你先猜测数字为 7 。

如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $7 。

如果我的数字更大，则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。

如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $9 。

如果我的数字更大，那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏，总费用为 $7 + $9 = $16 。

如果我的数字更小，那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏，总费用为 $7 + $9 = $16 。

如果我的数字更小，则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。

如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $3 。

如果我的数字更大，则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。

如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $5 。

如果我的数字更大，那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。

如果我的数字更小，那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。

如果我的数字更小，则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。

如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $1 。

如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $7 + $3 + $1 = $11 。

在最糟糕的情况下，你需要支付 $16 。因此，你只需要 $16 就可以确保自己赢得游戏。

示例 2：
输入：n = 1
输出：0
解释：只有一个可能的数字，所以你可以直接猜 1 并赢得游戏，无需支付任何费用。

示例 3：
输入：n = 2
输出：1
解释：有两个可能的数字 1 和 2 。

你可以先猜 1 。

如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $1 。

如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $1 。

最糟糕的情况下，你需要支付 $1 。

算法

我们要在 [1, n] 中猜数，当我们猜了 1 <= x <= n，确保获胜的最少现金数记为 z(x)，如果猜中，那么无费用，游戏结束。否则产生 x 费用，后续有两种可能

目标在 [1, x - 1]
目标在 [x + 1, n]

如果我们知道 [1, x - 1] 和 [x + 1, n] 中，最坏情况的费用，也就是确保获胜的最少现金数，分别记为记为 y1, y2

由于需要确保获胜，因此我们必须有 z(x) = max(x + y1, x + y2)，才能保证猜 x 后现金可以支撑到获胜。

我们可以在 x 的选择范围 [1, n] 中选一个使得 z(x) 最小的 x。

通过以上分析，我们发现本题虽然没有显式地给出两个人，但经过抽象后还是 minimax 的问题。

假设选择我们的猜数区间是 [i, j]，假想一个对手作为后手，

先手极小化的是，选择使得最后需要付出的总成本最小的 i <= x <= j
后手极大化的是，选择 [i, x-1], [x+1, j] 这两个子区间中最后需要付出的总成本最大的那个

基于以上分析，我们可以写出博弈 DP 算法

状态定义
dp[i][j] := 猜数区间为 [i, j]，确保获胜需要最小的现金数

答案
dp[1][n]

初始化
dp[i][i] = 0

状态转移
dp[i][j] = min(x + max(dp[i][x - 1], dp[x + 1][j])), i <= x <= j

代码

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int> > dp(n + 1, vector<int>(n + 1, INT_MAX));
        for(int i = 1; i <= n; ++i)
            dp[i][i] = 0;
        for(int j = 2; j <= n; ++j)
            for(int i = j - 1; i >= 1; --i)
            {
                dp[i][j] = min(dp[i + 1][j] + i, dp[i][j - 1] + j);
                for(int k = i + 1; k <= j - 1; ++k)
                    dp[i][j] = min(dp[i][j], max(dp[k + 1][j], dp[i][k - 1]) + k);
            }
        return dp[1][n];
    }
};

294. 翻转游戏 II

算法要点

minimax + 记忆化搜索

题目描述

你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：

给你一个字符串 currentState ，其中只含 ‘+’ 和 ‘-‘ 。你和朋友轮流将连续的两个 “++” 反转成 “—“ 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。默认每个人都会采取最优策略。

请你写出一个函数来判定起始玩家是否存在必胜的方案：如果存在，返回 true ；否则，返回 false 。

1
2
3

提示：
1 <= currentState.length <= 60
currentState[i] 不是 '+' 就是 '-'

示例 1：
输入：currentState = “++++”
输出：true
解释：起始玩家可将中间的 “++” 翻转变为 “+—+” 从而得胜。
示例 2：
输入：currentState = “+”
输出：false

算法

策梅洛定理(Zermelo’s theorem) 是博弈论的一条定理，以恩斯特·策梅洛命名。

在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中

那先行或后行者当中必有一方有必胜/必不败的策略。

以两个人下棋为例，策梅洛定理的意思是要么黑棋有必胜策略，要么白棋有必胜策略，要么双方有必不败策略

由策梅洛定理，我们可以说本题要么先手必胜，要么后手必胜。所以我们实际上就是要看初始状态 currentState 是否是必胜的。

假设当前状态为 s，如果 s 中没有连续的 ++，则 s 必败。adj(s) 为 s 中翻转某个 ++ 后可以到达的状态集合。如果 adj(s) 中的某个状态 t 都是必败的，那么 s 是必胜的，因为选择到达 t 就可以了。

基于以上分析，我们可以写出博弈 DP 算法，如下

状态定义
dp[s] := 状态 s 是否必胜

答案
dp[currentState]

初始化
dp[s] = false, s 中不含有 ++

状态转移
dp[s] = dp[s] || !dp[t], t in adj(s)

代码

class Solution {
public:
    bool canWin(string s) {
        int n = s.size();
        if(n < 2) return false;
        unordered_map<string, bool> dp;
        return solve(s, dp);
    }

private:
    bool solve(string& s, unordered_map<string, bool>& dp)
    {
        int n = s.size();
        if(dp.find(s) != dp.end()) // 该状态已经算过
            return dp[s];
        for(int i = 0; i < n - 1; ++i) // 枚举所有次态
        {
            if(s[i] == '+' && s[i + 1] == '+')
            {
                s[i] = '-';
                s[i + 1] = '-';
                bool f = solve(s, dp);
                s[i] = '+';
                s[i + 1] = '+';
                if(!f)
                    return dp[s] = true;
            }
        }
        return dp[s] = false;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法动态规划

博弈DP

877. 石子游戏 / 486. 预测赢家

题目描述

算法

代码

1908. Nim 游戏 II

题目描述

算法

代码

375. 猜数字大小 II

题目描述

算法

代码

294. 翻转游戏 II

题目描述

算法

代码