博弈型 | Civilization Museum

type

status

password

date

slug

summary

1 题型分析

1.1 题型

博弈就是两个人参与的游戏，一方先走

满足一定条件取胜

1.2 解法

状态：和其他不一样，从第一步开始分析

394 · 硬币排成线 - LintCode

n个硬币，每个人一次可以拿一个或者两个硬币，拿走最后一个硬币的人赢，给定n，求是否先手必赢？

输入: 4 输出: true 解释: 先手玩家第一轮拿走一个硬币, 此时还剩三个. 这时无论后手玩家拿一个还是两个, 下一次先手玩家都可以把剩下的硬币拿完

题解

本题一个人可以拿1个或者2个，如果输入的n符合条件，为了确保第一个人拿一定能够赢，则对拿法一定要有要求：第一个人在第一次拿之后一定要保证剩下的物品数量为3的倍数，接下来无论第二个人怎么拿，第一个人还是能把剩下的物品数量控制在3的倍数，因此第一个人一定能够确保自己拿到最后一枚硬币并获胜。因此对于输入的数n，n%3=0时为false，否则为true；

395 · 硬币排成线 II - LintCode

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。

输入: [1, 2, 2] 输出: true 解释: 先手玩家直接拿走两颗硬币即可.

题解一

这里介绍一下动态规划的解法：

要判断第一个玩家是否能够赢得比赛，我们就需要对玩家的不同拿法进行分析与判断，得到利润最大的那种拿法。因为针对玩家1的每一种拿法，玩家2会想出自己的拿法让玩家1接下去的获利最小，而对玩家1，就是要保证当前的拿法能够使剩下的硬币获利最大，因此我们需要从后往前通过记录后续拿法的最优解来进行动态规划。

建立数组DP[i]表示拿第i个硬币到第n个硬币所能获得的最大利润；

对于玩家拿到第i个硬币时，玩家拿硬币仍是从左往右拿。因此他有两种选择，仅拿第i个硬币或者拿第i个与第i+1个硬币，这两种拿法均会产生一个价值作为DP[i]的值；因为我们是从后往前进行动态规划，我们知道后续的结果，因此我们知道怎样的拿法会使得最终结果更好；

第二个玩家在我们做出选择后也会对第一个玩家的利益进行限制，例如当第一个玩家拿第i个硬币时，他可以拿第i+1个或拿第i+1、i+2个硬币，但是他会对的结果进行判断，保证第一个玩家的获利达到最小，即选择DP[i+2]和DP[i+3]中的最小值来决定自己是拿一个还是拿两个；

注意：如果第二个玩家拿第 i+1 个，那么第一个玩家的价值就是nums[i] + DP[i+2] 如果第二个玩家拿第 i+1、i+2 个，那么第一个玩家的价值就是nums[i] + DP[i+3]。

综上，动态规划表达式为：DP[i] = max{nums[i]+min{DP[i+2],DP[i+3]} , nums[i]+nums[i+1]+min{DP[i+3],DP[i+4]} };

题解二(思路与第三道题承接)

定义dp(i)为区间(i,n)先手玩家可以取到的最大硬币总价值。

定义sum(i,n)是从i到n的区间和

首先考虑dp(i),可以拿第i个硬币，从dp(i+1)转移过来。也可以拿第i、i+1两个个硬币，从第dp(i+2)转移过来。

dp方程为dp(i,j) = max(values[i] + sum(i+1) - dp(i+1,j) , values[i] + values[i+1] + sum(i+2) - dp(i+2))；因为dp[i]与dp[i+1]、dp[i+2]有关，所以需要从右向左遍历。

其中的values[i] + sum(i+1) - dp(i+1) 可以这样理解：我拿第i个硬币，values[i]是我拿到的数值，肯定要加上；再想区间[i+1,n]我能拿到的最大值是多少，由于我拿了第i个，所以区间[i+1,n]变成了对面先手，对面能够拿到最大值dp(i+1)，而我只能拿到sum(i+1)-dp(i+1)

values[i] + values[i+1] + sum(i+2) - dp(i+2)) 可以这样理解：我拿第i、i+1两个硬币，values[i]、values[i+1] 是我拿到的数值，肯定要加上；再想区间[i+2,n]我能拿到的最大值是多少，由于我拿了第i、i+1两个，所以区间[i+2]变成了对面先手，对面能够拿到最大值dp(i+2)，而我只能拿到sum(i+2)-dp(i+2)

396 · 硬币排成线 III - LintCode

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜.请判定 第一个玩家 会赢还是会输.

输入: [3, 2, 2] 输出: true 解释: 第一个玩家在刚开始的时候拿走 3, 然后两个人分别拿到一枚 2.

题解一

定义dp(i,j)为区间(i,j)先手玩家可以取到的最大硬币总价值。

定义sum(i,j)是从i到j的区间和

首先考虑dp(i,j),可以拿第i个硬币，从dp(i+1,j)转移过来。也可以拿第j个硬币，从第dp(i,j-1)转移过来。

dp方程为dp(i,j) = max(values[i] + sum(i+1,j) - dp(i+1,j) , values[j] + sum(i,j-1) - dp(i,j-1))。因为dp[i]与dp[i+1]有关，所以i需要从右向左遍历；因为dp[j]与dp[j-1]有关，所以j需要从左向右遍历。

其中的values[i] + sum(i+1,j) - dp(i+1,j) 可以这样理解：我拿第i个数值，values[i]是我拿到的数值，肯定要加上；再想区间(i+1,j)我能拿到的最大值是多少，由于我拿了第i个，所以区间(i+1,j)变成了对面先手，对面能够拿到最大值dp(i+1,j)，而我只能拿到sum(i+1,j)-dp(i+1,j)

由上述公式就可以写出代码了，时间复杂度，空间复杂度

可以使用滚动数组的方法对空间进行优化，达到的空间复杂度。