[Leetcode 486] Predict the Winner

作者 Shilei Tian 日期 2017-02-08
[Leetcode 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:

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.

解题思路

这是一道超级典型的动态规划题目,立马可以想到的是,player 1 得到的分数应该写成 p1 = max(? + nums[l], ? + nums[r]),其中 lr 分别是当前可以选择的区间。那么 ? 应该是什么呢?应该是 player 2 选完了以后得到的结果。那么从 player 1 的角度来考虑,如果他想赢,就一定得令 player 2 获得的分数最少。所以这个 ? 应该写成 ? = min(…) 这样的形式。所以该问题又变成了一个最大化最小值。如果这样考虑的话,就会非常麻烦。Solutions 中有一位朋友提到了 MIT OCW 一位老师讲的思路,点进去看了以后,顿时被他那印度口音的英语折服……听下来他的推导倒是没太懂,但是他说的一句话我听进去了:player 2 也想自己赢,他也是一个会各种策略的人。那么我们直接来模拟两个人博弈的过程不就可以了?

在其中的某一个时刻,我们设当前可以选择的范围是 [l, r],用 s1 来记录当前 player 1 得到的分数,s2 来记录 player 2 得到的分数。那么 player 1 可以选择左侧这个,他的分数就变成 s1 + nums[l],player 2 可选的范围就变成 [l + 1, r];如果 player 1 可以选择右侧那个,他的分数就变成 s1 + nums[r],player 2 可选的范围就变成 [l, r - 1]

好,这样 player 1 这一轮就选完了,轮到我们 player 2 来选,那么他可以获得的分数实际上套路都和 player 1 一样,这里我们就不赘述。那么我们这个什么时候算停呢?无论轮到哪个 player,如果他发现 l > r,那么他就不能选了,此时的分数就定格了。

最关键的地方来了!如果 player 1 想赢,是不是他就想 player 2 输?同样的道理,如果 player 2 想赢,是不是 player 1 就得输?那么我们可以写两个函数 player1player2,在 player1 中处理完后调用 player2 不就相当于模拟了 player 1 选完了以后交给 player 2 来选?同样,player2 处理完后再调用 player1 就相当于 player 2 选完了又轮到 player 1 选。函数的返回值就设定为该 player 能否赢。所以我们在写这两个函数的时候,要设身处地的考虑,每个人都想自己赢,所以只要对方赢了,自己就输了。所以将调用对方函数的返回值取反就可以得到自己的结果了。

这样说似乎不太明白,我们来直接看代码:

class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
return first(nums, 0, nums.size() - 1, 0, 0);
}
private:
bool first(const vector<int>& nums, int l, int r, int s1, int s2) {
if (l > r) {
return s1 >= s2;
}
return !second(nums, l + 1, r, s1 + nums[l], s2) || !second(nums, l, r - 1, s1 + nums[r], s2);
}
bool second(const vector<int>& nums, int l, int r, int s1, int s2) {
if (l > r) {
return s1 < s2;
}
return !first(nums, l + 1, r, s1, s2 + nums[l]) || !first(nums, l, r - 1, s1, s2 + nums[r]);
}
};

非常简洁的递归代码,我们先来分析 first,也就是 player 1 的函数。第一个参数不用说,第二个和第三个参数分别记录的是左右边界,第四个和第五个参数记录的是当前状态下 player 1 和 player 2 已经得到的分数。第 8 行先判断左边界是否超过右边界,如果是,就说明他没得选了,大局已定,只能看结果了,就判断,如果 s1(就是他自己的分数)大于等于 s2(就是 player 2 的分数),他就赢了;否则就输了。如果左右边界都正常,那么说明还可以继续选,所有下面就有了两个调用 second 函数的地方。我们两次调用就是对应取左边或者右边的边界这两种情况。取反的地方就是说,如果 player 2 赢了,那么 player 1 就输了,因为我们前面说,player 2 也想赢啊,并且我们下面的函数其实也是从 player 2 想赢的角度出发的呀!所以,player 1 想赢,必须 player 2 输,就有了这个取反。

再看 player 2 对应的函数 second,参数都一样,第 15 行进行判断,但是这里确实如果 s2 大的话,返回 true,这就是我所说的,设身处地为 player 2 着想,他想赢,必须 s2 大!下面两次递归调用道理就和上面 player 1 的一样了。

总结

严格意义上来说,上面的这种思路不算是一种动态规划的做法吧,应该就算是一种递归解法,但是容易理解!有时候,换位思考看起来也是可以用在算法的设计上面的……