Abo

从「石头游戏」到博弈类问题中的动态规划

所有石头被拿完后,谁拥有的石头多,谁获胜。

博奕问题 - - - 「假设两个人都足够聪明,最后谁会获胜」

wallhaven-nk67jd

流年安稳,世事无尘

游戏规则

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

假设你们都很聪明,由你第一个开始拿,请你写一个算法,输入一个数组 piles,返回你是否能赢(true 或 false)。

注意,石头的堆的数量为偶数,所以你们两人拿走的堆数一定是相同的。石头的总数为奇数,也就是你们最后不可能拥有相同多的石头,一定有胜负之分。

举个例子,piles=[2, 1, 9, 5],你先拿,可以拿 2 或者 5,你选择 2。

piles=[1, 9, 5],轮到对手,可以拿 1 或 5,他选择 5。

piles=[1, 9] 轮到你拿,你拿 9。

最后,你的对手只能拿 1 了。

这样下来,你总共拥有 2+9=11 颗石头,对手有 5+1=6 颗石头,你是可以赢的,所以算法应该返回 true。

你看到了,并不是简单的挑数字大的选,为什么第一次选择 2 而不是 5 呢?因为 5 后面是 9,你要是贪图一时的利益,就把 9 这堆石头暴露给对手了,那你就要输了。

这也是强调双方都很聪明的原因,算法也是求最优决策过程下你是否能赢。

这道题又涉及到两人的博弈,也可以用动态规划算法暴力试,比较麻烦。但我们只要对规则深入思考,就会大惊失色:只要你足够聪明,你是必胜无疑的,因为你是先手。

智力题解法

题目有两个条件很重要:一是石头总共有偶数堆,石头的总数是奇数。这两个看似增加游戏公平性的条件,反而使该游戏成为了一个割韭菜游戏。我们以 piles=[2, 1, 9, 5] 讲解,假设这四堆石头从左到右的索引分别是 1,2,3,4。

如果我们把这四堆石头按索引的奇偶分为两组,即第 1、3 堆和第 2、4 堆,那么这两组石头的数量一定不同,也就是说一堆多一堆少。因为石头的总数是奇数,不能被平分。

而作为第一个拿石头的人,你可以控制自己拿到所有偶数堆,或者所有的奇数堆。

你最开始可以选择第 1 堆或第 4 堆。如果你想要偶数堆,你就拿第 4 堆,这样留给对手的选择只有第 1、3 堆,他不管怎么拿,第 2 堆又会暴露出来,你就可以拿。同理,如果你想拿奇数堆,你就拿第 1 堆,留给对手的只有第 2、4 堆,他不管怎么拿,第 3 堆又给你暴露出来了。

也就是说,你可以在第一步就观察好,奇数堆的石头总数多,还是偶数堆的石头总数多,然后步步为营,就一切尽在掌控之中了。

睿智的代码解法

本文就借石头游戏来讲讲「假设两个人都足够聪明,最后谁会获胜」这一类问题该如何用动态规划算法解决。

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

博弈问题的难点在于,两个人要轮流进行选择,而且都贼精明,应该如何编程表示这个过程呢?

我们把「石头游戏」改的更具有一般性:

问题描述

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

假设双方实力相当,请你设计一个算法,返回先手和后手的最后得分(石头总数)之差。比如上面那个例子,先手能获得 4 分,后手会获得 100 分,你的算法应该返回 -96。

dp数组的定义

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

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

20191024230852

下文讲解时,认为元组是包含 first 和 second 属性的一个类,而且为了节省篇幅,将这两个属性简写为 fir 和 sec。比如按上图的数据,我们说

dp[1][3].fir = 10dp[0][1].sec = 3

1
2
3
4
5
dp[i][j].fir 表示,对于 piles[i...j]这部分石堆,先手能获得的最高分数
dp[i][j].sec 表示,对于 piles[i...j]这部分石堆,后手能获得的最高分
举例解释一下,假设piles=[3,9,1,2],索引从0开始
dp[0][1].fir=9 意味着:面对石头堆[3,9],先手最终能获得9
dp[1][3].sec=2 意味着:面对石头堆[9,1,2],后手最终能获得2

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

思考

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

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

20191024232430

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

20191024232437

11

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

22

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

33

代码实现🙄

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

1
2
3
4
5
6
7
class Pair {
int fir, sec;
Pair(int fir, int sec) {
this.fir = fir;
this.sec = sec;
}
}

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

44

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

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