LeetCode：486. 預(yù)測贏家

一、遞歸

注意到本題數(shù)據(jù)范圍為$1<=n<=20$，因此可以使用遞歸枚舉選擇方式，時間復(fù)雜度為$2^{20}=1024?1024=1048576=1.05\times 10^6$。

對于每一個先手都有兩種選擇方式，我們對該選擇方式進行枚舉。

我們定義遞歸函數(shù)$predict$表示玩家1在當(dāng)前選擇的情況下是否可以勝利，注意到每個玩家的玩法都會使他的分?jǐn)?shù)最大化，因此對于玩家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;}
};

二、區(qū)間動態(tài)規(guī)劃

注意到這里是從大的數(shù)組中選擇，讓數(shù)組依次減小，我們也可以從數(shù)組小的開始轉(zhuǎn)移到大數(shù)組，因為當(dāng)小數(shù)組確定時，大數(shù)組也能確定。

我們可以定義$dp1[i][j][player]$表示在選擇數(shù)組$[i,j]$時，$player$先手時，玩家1的分?jǐn)?shù)；類似的有$dp2[i][j][player]$。

則有狀態(tài)轉(zhuǎn)移：

//玩家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];}

時間復(fù)雜度：$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應(yīng)該效益要最低。
但這個邏輯感覺存在一定問題，因為玩家1先手，玩家1想要自己的效益最大，這個時候玩家2的效益是跟玩家1的選擇有關(guān)的，因為棋局完全根據(jù)玩家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];}
};