思路： 解法一： 转换比较拿取分数多少的思路，改为考虑 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; } };转载于:https://www.cnblogs.com/ruoh3kou/p/9893416.html
