力扣 | 递归 | 区间上的动态规划 | 486. 预测赢家

LeetCode：486. 预测赢家

一、递归

注意到本题数据范围为$1<=n<=20$，因此可以使用递归枚举选择方式，时间复杂度为$2^{20}=1024\ast 1024=1048576=1.05\times 10^6$。

对于每一个先手都有两种选择方式，我们对该选择方式进行枚举。

我们定义递归函数$predict$表示玩家1在当前选择的情况下是否可以胜利，注意到每个玩家的玩法都会使他的分数最大化，因此对于玩家2的选择，如果存在一个选择使得玩家1输，那么该情况下玩家1都不能胜利（只要玩家2选择让自己赢的情况，那么玩家1就不能赢了）。但是对于玩家1的选择，存在一个选择能赢就算可以赢。

class Solution {
public:bool predictTheWinner(vector<int>& nums) {return predict(nums, 0, (int) nums.size() - 1, 0, 0, 0);}
private:bool predict(vector<int> & nums, int left, int right, int player, int score_1, int score_2){if(left > right){if(score_1 >= score_2) return true;else return false;}if(player == 0){//玩家一，存在一个赢就算赢了if(predict(nums, left + 1, right, player ^ 1, score_1 + nums[left], score_2)) return true;if(predict(nums, left, right - 1, player ^ 1, score_1 + nums[right], score_2)) return true;}else{//玩家二，存在一个玩家二赢，则玩家一必输。if(predict(nums, left + 1, right, player ^ 1, score_1, score_2 + nums[left]) &&predict(nums, left, right - 1, player ^ 1, score_1, score_2 + nums[right])) return true;}return false;}
};

二、区间动态规划

注意到这里是从大的数组中选择，让数组依次减小，我们也可以从数组小的开始转移到大数组，因为当小数组确定时，大数组也能确定。

我们可以定义$dp1[i][j][player]$表示在选择数组$[i,j]$时，$player$先手时，玩家1的分数；类似的有$dp2[i][j][player]$。

则有状态转移：

//玩家1先手dp1[i][j][0] = max(dp1[i + 1][j][1] + nums[i], dp1[i][j - 1][1] + nums[j]);if(dp1[i + 1][j][1] + nums[i] >= dp1[i][j - 1][1] + nums[j]){dp2[i][j][0] = dp2[i + 1][j][1];if(dp1[i + 1][j][1] + nums[i] == dp1[i][j - 1][1] + nums[j])dp2[i][j][0] = min(dp2[i + 1][j][1], dp2[i][j - 1][1]);}else{dp2[i][j][0] = dp2[i][j - 1][1];}
//玩家2先手dp2[i][j][1] = max(dp2[i + 1][j][0] + nums[i], dp2[i][j - 1][0] + nums[j]);if(dp2[i + 1][j][0] + nums[i] >= dp2[i][j - 1][0] + nums[j]){dp1[i][j][1] = dp1[i + 1][j][0];if(dp2[i + 1][j][0] + nums[i] == dp2[i][j - 1][0] + nums[j])dp1[i][j][1] = min(dp1[i + 1][j][0], dp1[i][j - 1][0]);}else{dp1[i][j][1] = dp1[i][j - 1][0];}

时间复杂度：$O(N^2)$

class Solution {
public:bool predictTheWinner(vector<int>& nums) {vector<vector<array<int, 2>>> dp1(nums.size(), vector<array<int, 2>>(nums.size(), array<int, 2>{}));vector<vector<array<int, 2>>> dp2(nums.size(), vector<array<int, 2>>(nums.size(), array<int, 2>{}));for(int i = 0; i < nums.size(); ++ i){dp1[i][i][0] = nums[i];dp2[i][i][1] = nums[i];}for(int k = 1; k < nums.size(); ++ k){for(int i = 0; k + i < nums.size(); ++ i){int j = i + k;//玩家1先手dp1[i][j][0] = max(dp1[i + 1][j][1] + nums[i], dp1[i][j - 1][1] + nums[j]);if(dp1[i + 1][j][1] + nums[i] >= dp1[i][j - 1][1] + nums[j]){dp2[i][j][0] = dp2[i + 1][j][1];if(dp1[i + 1][j][1] + nums[i] == dp1[i][j - 1][1] + nums[j])dp2[i][j][0] = min(dp2[i + 1][j][1], dp2[i][j - 1][1]);}else{dp2[i][j][0] = dp2[i][j - 1][1];}//玩家2先手dp2[i][j][1] = max(dp2[i + 1][j][0] + nums[i], dp2[i][j - 1][0] + nums[j]);if(dp2[i + 1][j][0] + nums[i] >= dp2[i][j - 1][0] + nums[j]){dp1[i][j][1] = dp1[i + 1][j][0];if(dp2[i + 1][j][0] + nums[i] == dp2[i][j - 1][0] + nums[j])dp1[i][j][1] = min(dp1[i + 1][j][0], dp1[i][j - 1][0]);}else{dp1[i][j][1] = dp1[i][j - 1][0];}}}return dp1[0][(int) nums.size() - 1][0] >= dp2[0][(int) nums.size() - 1][0];}
};

简化代码：（这个代码过了）

简化逻辑：玩家1先手，那么玩家1效益最大，玩家2应该效益要最低。
但这个逻辑感觉存在一定问题，因为玩家1先手，玩家1想要自己的效益最大，这个时候玩家2的效益是跟玩家1的选择有关的，因为棋局完全根据玩家1来决定。所以一开始我并没有直接使用min求解后手。

class Solution {
public:bool predictTheWinner(vector<int>& nums) {vector<vector<array<int, 2>>> dp1(nums.size(), vector<array<int, 2>>(nums.size(), array<int, 2>{}));vector<vector<array<int, 2>>> dp2(nums.size(), vector<array<int, 2>>(nums.size(), array<int, 2>{}));for(int i = 0; i < nums.size(); ++ i){dp1[i][i][0] = nums[i];dp2[i][i][1] = nums[i];}for(int k = 1; k < nums.size(); ++ k){for(int i = 0; k + i < nums.size(); ++ i){int j = i + k;//玩家1先手dp1[i][j][0] = max(dp1[i + 1][j][1] + nums[i], dp1[i][j - 1][1] + nums[j]);dp2[i][j][0] = min(dp2[i + 1][j][1], dp2[i][j - 1][1]);//玩家2先手dp2[i][j][1] = max(dp2[i + 1][j][0] + nums[i], dp2[i][j - 1][0] + nums[j]);dp1[i][j][1] = min(dp1[i + 1][j][0], dp1[i][j - 1][0]);}}return dp1[0][(int) nums.size() - 1][0] >= dp2[0][(int) nums.size() - 1][0];}
};