题目描述
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数,随后玩家 2 继续从剩余数组任意一端拿取分数,然后玩家 1 拿,…… 。每次一个玩家只能拿取一个分数,分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组,预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
样例
输入:[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 。
算法1
(递归) $O(n^2)$
输入:数组
输出:先手玩家是否必胜
状态表示:
$f(i,j)$:集合,表示从i下标到j下标长度的数组中,先手玩家所能够获得的最大分数 - 右手玩家最大分数, 当大于0时,先手玩家胜
$i$: 下界,从$0$到$\lceil len/2 \rceil$
$j$: 上界,从$\lceil len/2 + 1 \rceil$到$\lceil len \rceil$
属性:分数
状态计算:
由于只能选择取最前或者最后的数,即两种选择,而且在对手取时,首先对手取的分会使我们的分数下降,因此是负的,另外取负号时可以把对我方最不利的选择,即max改成min(min-max游戏),因此在状态转移时可以加上负号,使得$max()$变成$min()$:
$$f(i, j) = max(-f(i+1, j)+f[i], -f(i, j-1)+f[j])$$
C++ 代码
class Solution {
public:
int f(int i, int j, vector<int>& nums)
{
if(i==j)
return nums[i];
return max(-f(i+1, j, nums)+nums[i], -f(i, j-1, nums)+nums[j]);
}
bool PredictTheWinner(vector<int>& nums) {
#ifdef _commet
int i = 0, j = nums.size() - 1;
return f(i, j, nums) >=0? true :false;
}
};
算法2
(动态规划) $O(n^2)$
从递归解法可以看出,我们的$f[i][j]$从$f[i+1][j]$和$f[i][j-1]$进行转移,即矩阵下边和左边相邻的元素。因此,我们只要先将矩阵对角线上的元素(即$f[0][0]$到$f[n-1][n-1]$)先进行初始化,然后再递推计算上三角矩阵元素即可(当$j$小于$i$时不存在数组,下三角部分不需要进行计算)。
C++ 代码
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> f(n,vector<int>(n));
for(int l = 1;l <= n;l++)
for(int i = 0; i + l -1 < n; i++)
{
int j = i + l - 1;
if (l == 1)
f[i][j] = nums[i];
else
{
f[i][j] = max(-f[i + 1][j] + nums[i], -f[i][j - 1] + nums[j]);
}
}
return f[0][n - 1] >=0 ? true: false;
}
};