经典动态规划:博弈问题
本文讲解的例题
LeetCode | 力扣 | 难度 |
---|---|---|
486. Predict the Winner | 486. 预测赢家 | 🟠 |
877. Stone Game | 877. 石子游戏 | 🟠 |
上一篇文章 几道智力题 中讨论到一个有趣的「石头游戏」,通过题目的限制条件,这个游戏是先手必胜的。但是智力题终究是智力题,真正的算法问题肯定不会是投机取巧能搞定的。所以,本文就借石头游戏来讲讲「假设两个人都足够聪明,最后谁会获胜」这一类问题该如何用动态规划算法解决。
博弈类问题的套路都差不多,下文参考 这个 YouTube 视频 的思路讲解,其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。掌握了这个技巧以后,别人再问你什么俩海盗分宝石,俩人拿硬币的问题,你就告诉别人:我懒得想,直接给你写个算法算一下得了。
我们把力扣第 877 题「石头游戏」改的更具有一般性:
你和你的朋友面前有一排石头堆,用一个数组 piles
表示,piles[i]
表示第 i
堆石子有多少个。你们轮流拿石头,一次拿一堆,但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后,谁拥有的石头多,谁获胜。
石头的堆数可以是任意正整数,石头的总数也可以是任意正整数,这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1, 100, 3]
,先手不管拿 1 还是 3,能够决定胜负的 100 都会被后手拿走,后手会获胜。
假设两人都很聪明,请你写一个 stoneGame
函数,返回先手和后手的最后得分(石头总数)之差。比如上面那个例子,先手能获得 4 分,后手会获得 100 分,你的算法应该返回 -96:
int stoneGame(int[] nums);
这样推广之后就变成了一道难度比较高的动态规划问题了,力扣第 486 题「预测赢家」就是一道类似的问题:
486. 预测赢家 | 力扣 | LeetCode |
给你一个整数数组 nums
。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合,玩家 1 先手。开始时,两个玩家的初始分值都是 0
。每一回合,玩家从数组的任意一端取一个数字(即,nums[0]
或 nums[nums.length - 1]
),取到的数字将会从数组中移除(数组长度减 1
)。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时,游戏结束。
如果玩家 1 能成为赢家,返回 true
。如果两个玩家得分相等,同样认为玩家 1 是游戏的赢家,也返回 true
。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1:
输入:nums = [1,5,2] 输出:false 解释:一开始,玩家 1 可以从 1 和 2 中进行选择。 如果他选择 2(或者 1 ),那么玩家 2 可以从 1(或者 2 )和 5 中进行选择。如果玩家 2 选择了 5 ,那么玩家 1 则只剩下 1(或者 2 )可选。 所以,玩家 1 的最终分数为 1 + 2 = 3,而玩家 2 为 5 。 因此,玩家 1 永远不会成为赢家,返回 false 。
示例 2:
输入:nums = [1,5,233,7] 输出:true 解释:玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个,玩家 1 都可以选择 233 。 最终,玩家 1(234 分)比玩家 2(12 分)获得更多的分数,所以返回 true,表示玩家 1 可以成为赢家。
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 107
函数签名如下:
boolean predictTheWinner(int[] nums);
bool predictTheWinner(vector<int>& nums);
def predictTheWinner(nums: List[int]) -> bool:
func predictTheWinner(nums []int) bool
var predictTheWinner = function(nums) {}
那么如果有了一个计算先手和后手分差的 stoneGame
函数,这道题的解法就直接出来了:
public boolean predictTheWinner(int[] nums) {
// 先手的分数大于等于后手,则能赢
return stoneGame(nums) >= 0;
}
bool predictTheWinner(vector<int>& nums) {
// 先手的分数大于等于后手,则能赢
return stoneGame(nums) >= 0;
}
def predictTheWinner(nums):
# 先手的分数大于等于后手,则能赢
return stoneGame(nums) >= 0
func predictTheWinner(nums []int) bool {
// 先手的分数大于等于后手,则能赢
return stoneGame(nums) >= 0
}
var predictTheWinner = function(nums) {
// 先手的分数大于等于后手,则能赢
return stoneGame(nums) >= 0;
}
这个 stoneGame
函数怎么写呢?博弈问题的难点在于,两个人要轮流进行选择,而且都贼精明,应该如何编程表示这个过程呢?其实不难,还是按照 动态规划核心框架 中强调多次的套路,首先明确 dp
数组的含义,然后只要找到「状态」和「选择」,一切就水到渠成了。
一、定义 dp
数组的含义
定义 dp
数组的含义是很有技术含量的,同一问题可能有多种定义方法,不同的定义会引出不同的状态转移方程,不过只要逻辑没有问题,最终都能得到相同的答案。
我建议不要迷恋那些看起来很牛逼,代码很短小的解法思路,最好是稳一点,采取可解释性最好,最容易推广的解法思路。本文就给出一种博弈问题的通用设计框架。
介绍 dp
数组的含义之前,我们先看一下 dp
数组最终的样子:
下文讲解时,认为元组是包含 first
和 second
属性的一个类,而且为了节省篇幅,将这两个属性简写为 fir
和 sec
。比如按上图的数据,我们说 dp[1][3].fir = 11
,dp[0][1].sec = 2
。
先回答几个读者可能提出的问题:
这个二维 dp table 中存储的是元组,怎么编程表示呢?这个 dp table 有一半根本没用上,怎么优化?很简单,都不要管,先把解题的思路想明白了再谈也不迟。
以下是对 dp 数组含义的解释:
dp[i][j].fir = x
表示,对于 piles[i...j]
这部分石头堆,先手能获得的最高分数为 x
。
dp[i][j].sec = y
表示,对于 piles[i...j]
这部分石头堆,后手能获得的最高分数为 y
。
举例理解一下,假设 piles = [2, 8, 3, 5]
,索引从 0 开始,那么:
dp[0][1].fir = 8
意味着:面对石头堆 [2, 8]
,先手最多能够获得 8 分;dp[1][3].sec = 5
意味着:面对石头堆 [8, 3, 5]
,后手最多能够获得 5 分。
我们想求的答案是先手和后手最终分数之差,按照这个定义也就是 dp[0][n-1].fir - dp[0][n-1].sec
,即面对整个 piles
,先手的最优得分和后手的最优得分之差。
二、状态转移方程
写状态转移方程很简单,首先要找到所有「状态」和每个状态可以做的「选择」,然后择优。
根据前面对 dp
数组的定义,状态显然有三个:开始的索引 i
,结束的索引 j
,当前轮到的人。
dp[i][j][fir or sec]
其中:
0 <= i < piles.length
i <= j < piles.length
对于这个问题的每个状态,可以做的选择有两个:选择最左边的那堆石头,或者选择最右边的那堆石头。 我们可以这样穷举所有状态:
n = piles.length
for 0 <= i < n:
for j <= i < n:
for who in {fir, sec}:
dp[i][j][who] = max(left, right)
上面的伪码是动态规划的一个大致的框架,这道题的难点在于,两人足够聪明,而且是交替进行选择的,也就是说先手的选择会对后手有影响,这怎么表达出来呢?
根据我们对 dp
数组的定义,很容易解决这个难点,写出状态转移方程:
dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
dp[i][j].fir = max( 选择最左边的石头堆 , 选择最右边的石头堆 )
# 解释:我作为先手,面对 piles[i...j] 时,有两种选择:
# 要么我选择最左边的那一堆石头 piles[i],局面变成了 piles[i+1...j],
# 然后轮到对方选了,我变成了后手,此时我作为后手的最优得分是 dp[i+1][j].sec
# 要么我选择最右边的那一堆石头 piles[j],局面变成了 piles[i...j-1]
# 然后轮到对方选了,我变成了后手,此时我作为后手的最优得分是 dp[i][j-1].sec
if 先手选择左边:
dp[i][j].sec = dp[i+1][j].fir
if 先手选择右边:
dp[i][j].sec = dp[i][j-1].fir
# 解释:我作为后手,要等先手先选择,有两种情况:
# 如果先手选择了最左边那堆,给我剩下了 piles[i+1...j]
# 此时轮到我,我变成了先手,此时的最优得分是 dp[i+1][j].fir
# 如果先手选择了最右边那堆,给我剩下了 piles[i...j-1]
# 此时轮到我,我变成了先手,此时的最优得分是 dp[i][j-1].fir
根据 dp 数组的定义,我们也可以找出 base case,也就是最简单的情况:
dp[i][j].fir = piles[i]
dp[i][j].sec = 0
其中 0 <= i == j < n
# 解释:i 和 j 相等就是说面前只有一堆石头 piles[i]
# 那么显然先手的得分为 piles[i]
# 后手没有石头拿了,得分为 0
这里需要注意一点,我们发现 base case 是斜着的,而且我们推算 dp[i][j]
时需要用到 dp[i+1][j]
和 dp[i][j-1]
:
根据前文 动态规划答疑篇 判断 dp
数组遍历方向的原则,算法应该倒着遍历 dp
数组:
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
dp[i][j] = ...
}
}
三、代码实现
如何实现这个 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;
}
}
class Pair {
public:
int fir, sec;
Pair(int fir, int sec) {
this->fir = fir;
this->sec = sec;
}
};
class Pair:
def __init__(self, fir: int, sec: int):
self.fir = fir
self.sec = sec
type Pair struct {
fir int
sec int
}
func NewPair(fir int, sec int) *Pair {
return &Pair{fir, sec}
}
function Pair(fir, sec) {
this.fir = fir;
this.sec = sec;
}
然后直接把我们的状态转移方程翻译成代码即可,注意我们要倒着遍历数组:
// 返回游戏最后先手和后手的得分之差
int stoneGame(int[] piles) {
int n = piles.length;
// 初始化 dp 数组
Pair[][] dp = new Pair[n][n];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
dp[i][j] = new Pair(0, 0);
// 填入 base case
for (int i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
// 倒着遍历数组
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 先手选择最左边或最右边的分数
int left = piles[i] + dp[i+1][j].sec;
int right = piles[j] + dp[i][j-1].sec;
// 套用状态转移方程
// 先手肯定会选择更大的结果,后手的选择随之改变
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i+1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j-1].fir;
}
}
}
Pair res = dp[0][n-1];
return res.fir - res.sec;
}
#include <iostream>
#include <algorithm>
using namespace std;
class Pair {
public:
int fir, sec;
Pair(int fir, int sec) {
this->fir = fir;
this->sec = sec;
}
};
// 返回游戏最后先手和后手的得分之差
int stoneGame(vector<int>& piles) {
int n = piles.size();
// 初始化 dp 数组
vector<vector<Pair>> dp(n, vector<Pair>(n, Pair(0, 0)));
// 填入 base case
for (int i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
// 倒着遍历数组
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 先手选择最左边或最右边的分数
int left = piles[i] + dp[i+1][j].sec;
int right = piles[j] + dp[i][j-1].sec;
// 套用状态转移方程
// 先手肯定会选择更大的结果,后手的选择随之改变
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i+1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j-1].fir;
}
}
}
Pair res = dp[0][n-1];
return res.fir - res.sec;
}
# 返回游戏最后先手和后手的得分之差
def stoneGame(piles: List[int]) -> int:
n = len(piles)
# 初始化 dp 数组
dp = [[Pair(0, 0) for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(i, n):
dp[i][j] = Pair(0, 0)
# 填入 base case
for i in range(n):
dp[i][i].fir = piles[i]
dp[i][i].sec = 0
# 倒着遍历数组
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
# 先手选择最左边或最右边的分数
left = piles[i] + dp[i+1][j].sec
right = piles[j] + dp[i][j-1].sec
# 套用状态转移方程
# 先手肯定会选择更大的结果,后手的选择随之改变
if left > right:
dp[i][j].fir = left
dp[i][j].sec = dp[i+1][j].fir
else:
dp[i][j].fir = right
dp[i][j].sec = dp[i][j-1].fir
res = dp[0][n-1]
return res.fir - res.sec
// 返回游戏最后先手和后手的得分之差
func stoneGame(piles []int) int {
n := len(piles)
// 初始化 dp 数组
dp := make([][]Pair, n)
for i := 0; i < n; i++ {
dp[i] = make([]Pair, n)
for j := 0; j < n; j++ {
dp[i][j] = Pair{0, 0}
}
}
// 填入 base case
for i := 0; i < n; i++ {
dp[i][i].fir = piles[i]
dp[i][i].sec = 0
}
// 倒着遍历数组
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
// 先手选择最左边或最右边的分数
left := piles[i] + dp[i+1][j].sec
right := piles[j] + dp[i][j-1].sec
// 套用状态转移方程
// 先手肯定会选择更大的结果,后手的选择随之改变
if left > right {
dp[i][j].fir = left
dp[i][j].sec = dp[i+1][j].fir
} else {
dp[i][j].fir = right
dp[i][j].sec = dp[i][j-1].fir
}
}
}
res := dp[0][n-1]
return res.fir - res.sec
}
var stoneGame = function(piles) {
const n = piles.length;
// 初始化 dp 数组
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => new Pair(0, 0)));
// 填入 base case
for (let i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
// 倒着遍历数组
for (let i = n - 2; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
// 先手选择最左边或最右边的分数
const left = piles[i] + dp[i+1][j].sec;
const right = piles[j] + dp[i][j-1].sec;
// 套用状态转移方程
// 先手肯定会选择更大的结果,后手的选择随之改变
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i+1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j-1].fir;
}
}
}
const res = dp[0][n-1];
return res.fir - res.sec;
};
动态规划解法,如果没有状态转移方程指导,绝对是一头雾水,但是根据前面的详细解释,读者应该可以清晰理解这一大段代码的含义。
而且,注意到计算 dp[i][j]
只依赖其左边和下边的元素,所以说肯定有优化空间,转换成一维 dp,想象一下把二维平面压扁,也就是投影到一维。但是,一维 dp
比较复杂,可解释性比较差,大家就不必浪费这个时间去理解了。
四、最后总结
本文给出了解决博弈问题的动态规划解法。博弈问题的前提一般都是在两个聪明人之间进行,编程描述这种游戏的一般方法是二维 dp 数组,数组中通过元组分别表示两人的最优决策。
之所以这样设计,是因为先手在做出选择之后,就成了后手,后手在对方做完选择后,就变成了先手。这种角色转换使得我们可以重用之前的结果,典型的动态规划标志。
读到这里的朋友应该能理解算法解决博弈问题的套路了。学习算法,一定要注重算法的模板框架,而不是一些看起来牛逼的思路,也不要奢求上来就写一个最优的解法。不要舍不得多用空间,不要过早尝试优化,不要惧怕多维数组。dp
数组就是存储信息避免重复计算的,随便用,直到咱满意为止。