原题
思路：
解法一：
转换比较拿取分数多少的思路，改为考虑 player拿的分数为正，把Player2拿的视为负，加上所有分数，如果最后结果大于0则Player1赢。
思考得出递归表达式：max(nums[beg] - player2(beg + 1, end), nums[end] - player2(beg, end + 1))
此解法效率很差 104ms，beats 5.32%
class Solution {
public:
bool PredictTheWinner(vector<int> &nums) {
return helper(0, nums.size() - 1, nums) >= 0;
}
int helper(int beg, int end, vector<int> &nums) {
if (beg >= end) return nums[beg];
return max(nums[beg] - helper(beg + 1, end, nums),
nums[end] - helper(beg, end - 1, nums));
}
};
解法二：
discussing里看到的利用dp结合MiniMax的优解
class Solution {
public:
int findwin(vector<int>&v, int left, int right, vector<vector<int>>& dp){
if(left > right)
return 0;
if(dp[left][right] != -1)
return dp[left][right];
int pos1 = v[left] + min(findwin(v, left + 2, right, dp), findwin(v, left+1, right-1, dp));
int pos2 = v[right] + min(findwin(v, left+1, right-1, dp), findwin(v, left, right-2, dp));
return dp[left][right] = max(pos1, pos2);
}
bool PredictTheWinner(vector<int>& v) {
if(v.size() == 0)
return false;
if(v.size() == 1)
return true;
vector<vector<int>> dp(v.size(), vector<int>(v.size(), -1));
int left = 0;
int right = v.size()-1;
int player1 = findwin(v, left, right, dp);
int sum = 0;
for(int i=0; i<v.size(); i++)
sum += v[i];
return player1 >= sum - player1;
}
};