动态规划之博弈问题

电玩女神 2021-11-09 05:10 311阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

作者 | labuladong

来源 | labuladong

博弈类问题的套路都差不多，下文举例讲解，其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。掌握了这个技巧以后，别人再问你什么俩海盗分宝石，俩人拿硬币的问题，你就告诉别人：我懒得想，直接给你写个算法算一下得了。

举个例子：

你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles\[i\] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。

石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 `piles = [1,100,3]`，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。

**假设两人都很聪明**，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。

这样推广之后，这个问题算是一道 Hard 的动态规划问题了。**博弈问题的难点在于，两个人要轮流进行选择，而且都贼精明，应该如何编程表示这个过程呢？**

### 一、定义 dp 数组的含义 ###

定义 dp 数组的含义是很有技术含量的，同一问题可能有多种定义方法，不同的定义会引出不同的状态转移方程，不过只要逻辑没有问题，最终都能得到相同的答案。

我建议不要迷恋那些看起来很牛逼，代码很短小的奇技淫巧，最好是稳一点，采取可解释性最好，最容易推广的设计思路。本文就给出一种博弈问题的通用设计框架。

介绍 dp 数组的含义之前，我们先看一下 dp 数组最终的样子：

![640?wx\_fmt=png][640_wx_fmt_png]

下文讲解时，认为元组是包含 first 和 second 属性的一个类，而且为了节省篇幅，将这两个属性简写为 fir 和 sec。比如按上图的数据，我们说 `dp[1][3].fir = 10`，`dp[0][1].sec = 3`。

先回答几个读者可能提出的问题：

这个二维 dp table 中存储的是元组，怎么编程表示呢？这个 dp table 有一半根本没用上，怎么优化？很简单，都不要管，先把解题的思路想明白了再谈也不迟。

**以下是对 dp 数组含义的解释：**

![640?wx\_fmt=png][640_wx_fmt_png 1]

我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 *dp*\[0\]\[*n*−1\].*f**i**r*−*dp*\[0\]\[*n*−1\].*sec*

### 二、状态转移方程 ###

写状态转移方程很简单，首先要找到所有「状态」和每个状态可以做的「选择」，然后择优。

根据前面对 dp 数组的定义，**状态显然有三个：****开始的索引 i，结束的索引 j，当前轮到的人。**

dp[i][j][fir or sec]其中：0 <= i < piles.lengthi <= j < piles.length
    其中：
    0 <= i < piles.length
    i <= j < piles.length

对于这个问题的每个状态，可以做的**选择有两个：****选择最左边的那堆石头，或者选择最右边的那堆石头。** 我们可以这样穷举所有状态：

![640?wx\_fmt=png][640_wx_fmt_png 2]

上面的伪码是动态规划的一个大致的框架，股票系列问题中也有类似的伪码。这道题的难点在于，两人是交替进行选择的，也就是说先手的选择会对后手有影响，这怎么表达出来呢？

根据我们对 dp 数组的定义，很容易解决这个难点，**写出状态转移方程：**

![640?wx\_fmt=png][640_wx_fmt_png 3]

根据 dp 数组的定义，我们也可以找出 **base case**，也就是最简单的情况：

![640?wx\_fmt=png][640_wx_fmt_png 4]

![640?wx\_fmt=png][640_wx_fmt_png 5]

这里需要注意一点，我们发现 base case 是斜着的，而且我们推算 dp\[i\]\[j\] 时需要用到 dp\[i+1\]\[j\] 和 dp\[i\]\[j-1\]：

![640?wx\_fmt=png][640_wx_fmt_png 6]

所以说算法不能简单的一行一行遍历 dp 数组，**而要斜着遍历数组：**

![640?wx\_fmt=png][640_wx_fmt_png 7]

说实话，斜着遍历二维数组说起来容易，你还真不一定能想出来怎么实现，不信你思考一下？这么巧妙的状态转移方程都列出来了，要是不会写代码实现，那真的很尴尬了。

### 三、代码实现 ###

如何实现这个 fir 和 sec 元组呢，你可以用 python，自带元组类型；或者使用 C++ 的 pair 容器；或者用一个三维数组 `dp[n][n][2]`，最后一个维度就相当于元组；或者我们自己写一个 Pair 类：

class Pair {    int fir, sec;    Pair(int fir, int sec) {        this.fir = fir;        this.sec = sec;    }}
        int fir, sec;
        Pair(int fir, int sec) {
        
            this.fir = fir;
            this.sec = sec;
        }
    }

然后直接把我们的状态转移方程翻译成代码即可，可以注意一下斜着遍历数组的技巧：

![640?wx\_fmt=png][640_wx_fmt_png 8]

动态规划解法，如果没有状态转移方程指导，绝对是一头雾水，但是根据前面的详细解释，读者应该可以清晰理解这一大段代码的含义。

而且，注意到计算 `dp[i][j]` 只依赖其左边和下边的元素，所以说肯定有优化空间，转换成一维 dp，想象一下把二维平面压扁，也就是投影到一维。但是，一维 dp 比较复杂，可解释性很差，大家就不必浪费这个时间去理解了。

### 四、最后总结 ###

本文给出了解决博弈问题的动态规划解法。博弈问题的前提一般都是在两个聪明人之间进行，编程描述这种游戏的一般方法是二维 dp 数组，数组中通过元组分别表示两人的最优决策。

之所以这样设计，是因为先手在做出选择之后，就成了后手，后手在对方做完选择后，就变成了先手。**这种角色转换使得我们可以重用之前的结果**，典型的动态规划标志。

读到这里的朋友应该能理解算法解决博弈问题的套路了。学习算法，一定要注重算法的模板框架，而不是一些看起来牛逼的思路，也不要奢求上来就写一个最优的解法。不要舍不得多用空间，不要过早尝试优化，不要惧怕多维数组。dp 数组就是存储信息避免重复计算的，随便用，直到咱满意为止。

希望本文对你有帮助。

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png 9]

[640]: /images/20211109/8339e06e782348289818449e5758dc75.png
[640_wx_fmt_png]: /images/20211109/a8fc2feaab3249bb935fb919b2592856.png
[640_wx_fmt_png 1]: /images/20211109/7c69b4cbf6964103a5a3f99a4d7c60e5.png
[640_wx_fmt_png 2]: /images/20211109/ace3e9e85e5d4637b8d14e3047e92e07.png
[640_wx_fmt_png 3]: /images/20211109/e9c33fa099cb47cabdb6d4c1c8435606.png
[640_wx_fmt_png 4]: /images/20211109/a43912be3a9948029da79d5af9039eb2.png
[640_wx_fmt_png 5]: /images/20211109/6acb92d3f6fc4ee3b6ec105bf5b85e08.png
[640_wx_fmt_png 6]: /images/20211109/e34ef56264d448c18e66e676e62ed105.png
[640_wx_fmt_png 7]: /images/20211109/863653d5ada747cf82c5a96061c0b437.png
[640_wx_fmt_png 8]: /images/20211109/296195109c6e4494899be170ec1fc109.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png 9]: /images/20211109/3d48f30c50154f9a94bb1dcfa32ffb74.png