LeetCode Predict the Winner Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins. Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score. Example 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

1. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

---

有关博弈论的题。有两个人A和B，每个人每次能从数组开始或结束位置拿掉一个数，A先拿，谁拿的数字之和越大获胜，问A是否可以获胜。 因为每个人都尽最大的努力想要获胜，所以如果A拿了num[0]，那么B从剩余的nums[1~n-1]拿数字的过程相当于A从nums[0~n-1]拿数字的过程，所以最优化拿数字的过程是一样的。 假设子问题为A从区间nums[s,…,e]拿数字尽量使自己赢，那么如果s==e，只有一个元素，则A拿到的元素和就为这个元素nums[s]。否则A可以尝试拿首元素nums[s]，此时B尽力从nums[s+1,…,e]中拿使B自己赢，所以A的收益就是nums[s]减去B从nums[s+1,…,e]拿到的收益；A也可以拿尾元素nums[e]，此时B尽力从nums[s,…,e-1]中拿使B自己赢，所以A的收益就是nums[e]减去B从nums[s,…,e-1]拿到的收益。A的最大收益就是拿首元素或尾元素获得的收益的较大值，如果大于等于0，说明A可以获胜。 递归代码如下： [cpp] class Solution { private: int helper(vector<int>& nums, int s, int e) { if (s == e)return nums[s]; else return max(nums[s] – helper(nums, s + 1, e), nums[e] – helper(nums, s, e – 1)); } public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); return helper(nums, 0, n – 1) >= 0; } }; [/cpp] 本代码提交AC，用时96MS。 还有一种更清晰的DP方法。假设dp[s][e]为A从区间nums[s,…,e]拿获得的最大收益，如果A拿首元素nums[s]，则获得的收益为nums[s]-dp[s+1][e]，因为B要从剩余的nums[s+1,..,e]拿尽量使自己赢，就相当于A从nums[s+1,…,e]要使自己赢，所以过程都是一样的，dp[s+1][e]就是B的收益。类似的，如果A拿尾元素，则获得的收益为nums[e]-dp[s][e-1]。所以有： $$!dp[s][e]=max(nums[s]-dp[s+1][e],nums[e]-dp[s][e-1])$$ 因为大区间的dp[s][e]会用到较小区间的dp[s+1][e]和dp[s][e-1]，所以可以区间长度进行DP，先求出小区间的值，求大区间时直接用小区间的值就好了。 代码如下： [cpp] class Solution { public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i)dp[i][i] = nums[i]; // 长度为0 for (int len = 1; len < n; ++len) { for (int s = 0; s + len < n; ++s) { dp[s][s + len] = max(nums[s] – dp[s + 1][s + len], nums[s + len] – dp[s][s + len – 1]); } } return dp[0][n – 1] >= 0; } }; [/cpp] 本代码提交AC，用时3MS。比递归版本快了很多。]]>