486. 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:**

1
2
3
4
5
6
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:**
1
2
3
4
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. 这道题一开始还以为会有什么特殊的技巧来处理,自己想了很久也没想出来。后来看了网上的答案,发现是把所有结果都遍历一遍的。处理的方法是递归或动态规划。递归方法如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
return canWin(nums, 0, 0, 1);
}

bool canWin(vector<int> nums, int sum1, int sum2, int player) {
if (nums.empty()) return sum1 >= sum2;
if (nums.size() == 1) {
if (player == 1) return sum1 + nums[0] >= sum2;
else if (player == 2) return sum2 + nums[0] > sum1;
}
vector<int> va = vector<int>(nums.begin() + 1, nums.end());
vector<int> vb = vector<int>(nums.begin(), nums.end() - 1);
if (player == 1) {
return !canWin(va, sum1 + nums[0], sum2, 2) || !canWin(vb, sum1 + nums.back(), sum2, 2);
} else if (player == 2) {
return !canWin(va, sum1, sum2 + nums[0], 1) || !canWin(vb, sum1, sum2 + nums.back(), 1);
}
}

};
结果:40ms,20.47%。效率不是很高。递归效率低的原因在于重复计算。因此可以通过保存中间结果,再次遇到相同情况时直接返回不用再次计算,提高了运算效率。代码从网上找了,代码如下。但仍看不懂中间结果是什么意思。另外找了一段:假设所有分数的总和为sum,那么最后一定是玩家1选择了一部分,玩家2选择了另外一部分,我们只需要玩家1的分数大于玩家2就可以了,那么可以想象成,每次玩家1选择了一个分数,就是加一个分数,轮到玩家2选择时,就是减去一个分数,判断最后剩下的数字的正负就可以知道玩家1是否赢了。我们另外创建一个函数,用来递归计算每次的加分数和减分数,最终值的正负就是赢与否,注意题目说分数相等也是玩家1赢,所以最后如果等于0,也是玩家1赢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
return canWin(nums, 0, n - 1, dp) >= 0;
}

int canWin(vector<int>& nums, int s, int e, vector<vector<int>>& dp) {
if (dp[s][e] == -1) {
dp[s][e] = (s == e) ? nums[s] : max(nums[s] - canWin(nums, s + 1, e, dp), nums[e] - canWin(nums, s, e - 1, dp));
}
return dp[s][e];
}

};
代码解释:
1
2
3
4
5
dp[s][e] = (s == e) ? nums[s] : max(nums[s] - canWin(nums, s + 1, e, dp), nums[e] - canWin(nums, s, e - 1, dp))

当s等于e时,递归的末端,只有一个数,玩家1与玩家2相减的数等于这个数;
当s不等于e时,玩家1选择nums[s],则玩家2在剩余数组中进行选择(递归)。采用max函数限定递归返回最大值。
因此,canWin函数的作用是递归计算加分数;dp数组的作用是存储某区间内的最优加分数。
结果:0ms, 100%.效率提升相当明显。