Fork me on GitHub

数据结构与算法-9-动态规划-博弈系列

博弈类问题的套路都差不多,其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果(俩海盗分宝石,俩人拿硬币的问题)。

「石头游戏」:

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

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

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

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

1、定义dp数组的含义

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp16.jpg

dp数组解释:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp17.jpg

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

2、状态转移方程

状态:开始的索引 i,结束的索引 j,当前轮到的人。

1
2
3
4
dp[i][j][fir or sec]
其中:
0 <= i < piles.length
i <= j < piles.length

选择有两个:选择最左边的那堆石头,或者选择最右边的那堆石头

穷举所有状态:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp18.jpg

状态转移方程:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp19.jpg

base case:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp20.jpg

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp21.jpg

推算 dp[i][j] 时需要用到 dp[i+1][j] 和 dp[i][j-1]:所以需要斜着遍历数组

3、实现

1
2
class Solution:
def stoneGame(self, piles: List[int]) -> bool:

返回先手和后手的得分之差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
n=len(piles)
dp=[[[0]*2 for i in range(n)] for i in range(n)] # 初始化dp

# 初始值
for i in range(n):
dp[i][i][0]=piles[i]

for i in range(n):
dp[i][i][0]=piles[i]
dp[i][i][1]=0

# 斜着遍历数组
for t in range(2,n+1):
for i in range(n-t+1):
j=t+i-1

# 先手选择最左边或者最右边的分数
left=piles[i]+dp[i+1][j][1]
right=piles[j]+dp[i][j-1][1]

# 状态转移
if left > right:
dp[i][j][0]=left
dp[i][j][1]=dp[i+1][j][0]
else:
dp[i][j][0]=right
dp[i][j][1]=dp[i][j-1][0]
res=dp[0][n-1]
return res[0] - res[1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
n=len(piles)
dp=[[[0]*2 for i in range(n)] for i in range(n)]
for i in range(n):
dp[i][i][0]=piles[i]

for i in range(n):
dp[i][i][0]=piles[i]
dp[i][i][1]=0

for i in range(n-1,-1,-1):
for j in range(i,n):
if i==j:
continue

left=piles[i]+dp[i+1][j][1]
right=piles[j]+dp[i][j-1][1]

if left >= right:
dp[i][j][0]=left
dp[i][j][1]=dp[i+1][j][0]
else:
dp[i][j][0]=right
dp[i][j][1]=dp[i][j-1][0]
res=dp[n-1][n-1]
return res[0] - res[1]

877. 石子游戏

链接:https://leetcode-cn.com/problems/stone-game/

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。

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

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

假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。

示例:

输入:[5,3,4,5]
输出:true
解释:
亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗,这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。
这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true 。 

提示:

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
n=len(piles)
dp=[[[0]*2 for i in range(n)] for i in range(n)]
for i in range(n):
dp[i][i][0]=piles[i]

for i in range(n):
dp[i][i][0]=piles[i]
dp[i][i][1]=0

for i in range(n-1,-1,-1):
for j in range(i,n):
if i==j:
continue

left=piles[i]+dp[i+1][j][1]
right=piles[j]+dp[i][j-1][1]

if left >= right:
dp[i][j][0]=left
dp[i][j][1]=dp[i+1][j][0]
else:
dp[i][j][0]=right
dp[i][j][1]=dp[i][j-1][0]
res=dp[n-1][n-1]
return res[0] > res[1]

题目有两个条件很重要:一是石头总共有偶数堆,石头的总数是奇数。这两个看似增加游戏公平性的条件,反而使该游戏成为了一个割韭菜游戏。

先手必胜!

1
2
3
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
return True
支持,让我的文章更加优秀!