486. Predict the Winner

一、题目简述

给定一个非负元素的数组，玩家1从该数组的两端选取一个数字，玩家2之后从剩余的数组两端选取，玩家1之后进行相同操作。玩家每次选择的数字在下一轮将不能继续使用。游戏结束直到所有的数字被取完。取得数字之和最大的玩家获胜。

对于给定数组，判断玩家1能否获胜，假设每个玩家都以能够获得最大成绩的方式取数。

例1：

输入：[1, 5, 2]输出： False解释：第一轮玩家1可以选择1或2。无论玩家1选择1（或2），玩家2都会从数组[5, 2]（[1, 5]）中选择5，之后玩家1选择2（或1）。最终玩家1得分1+2=3，玩家2得分5。 因此玩家1最终都不能取胜，返回Fasle。

示例2：

输入：[1, 5, 233, 7]输出：True解释：玩家1第一次选择1，玩家2从5或7之间选择。无论玩家2选择哪一个，玩家1都将会选择233。最终玩家1得分较高，返回True。

注意：

1≤ 数组长度 ≤ 20。数组元素非负，并且最大不会超过10,000,000。如果两个玩家得分相同，依然算玩家1获胜。

函数原型：bool PredictTheWinner(vector<int>& nums)

二、编程思路

本题可以使用动态规划进行编程。

状态定义：令dp[i][j]表示玩家在nums数组从下标i到j的子序列中能够取得的最大分数。令 sum[i]=∑k=i−1k=0nums[k] ；为了方便表示，使用 sums(i,j)=∑k=jk=inums[k] ，则有 sums(i,j)=sum[j+1]−sum[i] 。状态转移方程： 当i=j时，dp[i][j]=nums[i]； 当i < <script type="math/tex" id="MathJax-Element-849"><</script>j时，dp[i][j]=max{nums[i]+sums(i+1,j)-dp[i+1][j], nums[j]+sums(i,j-1)-dp[i][j-1]}； nums[i]+sums(i+1,j)-dp[i+1][j]表示玩家1选择nums[i]的情况，sums(i+1,j)-dp[i+1][j]表示在下一步玩家2选择时，其取得的最大分数为dp[i+1][j]，玩家1的分数则为[i+1,j]中的总分数减去玩家2的得分。后半部分同上。

三、代码实现

class Solution { public: bool PredictTheWinner(vector<int>& nums) { int size=nums.size(); vector<int> sum(size,0); vector<vector<int> >dp(size,vector<int>(size,0)); int tmp=0; for(int i=0;i<size;i++){ tmp+=nums[i]; sum[i]=tmp; } for(int i=0;i<size;i++){ dp[i][i]=nums[i]; } for(int i=1;i<size;i++){ for(int j=i+1;j<size;j++){ dp[i][j]=max((sum[j-1]-sum[i-1]-dp[i][j-1]+nums[j]), (sum[j]-sum[i]-dp[i+1][j]+nums[i])); } } return (dp[0][size-1]>=sum[size-1]/2.); } };

四、参考资料

486 Solutions