486 Predict the Winner 預(yù)測贏家
Description:
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:
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.
Constraints:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.
題目描述:
給定一個(gè)表示分?jǐn)?shù)的非負(fù)整數(shù)數(shù)組。 玩家 1 從數(shù)組任意一端拿取一個(gè)分?jǐn)?shù)，隨后玩家 2 繼續(xù)從剩余數(shù)組任意一端拿取分?jǐn)?shù)，然后玩家 1 拿，…… 。每次一個(gè)玩家只能拿取一個(gè)分?jǐn)?shù)，分?jǐn)?shù)被拿取之后不再可取。直到?jīng)]有剩余分?jǐn)?shù)可取時(shí)游戲結(jié)束。最終獲得分?jǐn)?shù)總和最多的玩家獲勝。
給定一個(gè)表示分?jǐn)?shù)的數(shù)組，預(yù)測玩家1是否會成為贏家。你可以假設(shè)每個(gè)玩家的玩法都會使他的分?jǐn)?shù)最大化。
示例 :
示例 1：
輸入：[1, 5, 2]
輸出：False
解釋：一開始，玩家1可以從1和2中進(jìn)行選擇。
如果他選擇 2（或者 1 ），那么玩家 2 可以從 1（或者 2 ）和 5 中進(jìn)行選擇。如果玩家 2 選擇了 5 ，那么玩家 1 則只剩下 1（或者 2 ）可選。
所以，玩家 1 的最終分?jǐn)?shù)為 1 + 2 = 3，而玩家 2 為 5 。
因此，玩家 1 永遠(yuǎn)不會成為贏家，返回 False 。
示例 2：
輸入：[1, 5, 233, 7]
輸出：True
解釋：玩家 1 一開始選擇 1 。然后玩家 2 必須從 5 和 7 中進(jìn)行選擇。無論玩家 2 選擇了哪個(gè)，玩家 1 都可以選擇 233 。
最終，玩家 1（234 分）比玩家 2（12 分）獲得更多的分?jǐn)?shù)，所以返回 True，表示玩家 1 可以成為贏家。
提示:
1 <= 給定的數(shù)組長度 <= 20.
數(shù)組里所有分?jǐn)?shù)都為非負(fù)數(shù)且不會大于 10000000 。
如果最終兩個(gè)玩家的分?jǐn)?shù)相等，那么玩家 1 仍為贏家。
思路:
- 遞歸
只用考慮玩家 1的操作是否能贏就行
用一個(gè)標(biāo)記記錄是否是玩家 1拿的
從兩邊分別取數(shù)字比較兩個(gè)玩家拿的數(shù)字之和的大小
時(shí)間復(fù)雜度O(2 ^ n), 空間復(fù)雜度O(n) - 動態(tài)規(guī)劃
dp[i][j]表示從 nums的區(qū)間 [i, j]中玩家 1能取到的最大領(lǐng)先
對于選擇 i的情況為 nums[i] - dp[i + 1][j]
對于選擇 j的情況為 nums[j] - dp[i][j - 1]
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
初始化 dp[i][i] = nums[i]即對角線上的數(shù)字對應(yīng)為 nums中的元素
注意到 dp只由前一行決定, 可以將空間壓縮到 O(n)
時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(n)
代碼:
C++:
class Solution
{
public:
bool PredictTheWinner(vector<int>& nums)
{
return dfs(0, 0, 0, nums.size() - 1, nums, 1);
}
private:
bool dfs(int sum1, int sum2, int l, int r, vector<int>& nums, bool flag)
{
if (l > r) return sum1 >= sum2;
if (flag) return dfs(sum1 + nums[l], sum2, l + 1, r, nums, !flag) or dfs(sum1 + nums[r], sum2, l, r - 1, nums, !flag);
return dfs(sum1, sum2 + nums[l], l + 1, r, nums, !flag) and dfs(sum1, sum2 + nums[r], l, r - 1, nums, !flag);
}
};
Java:
class Solution {
public boolean PredictTheWinner(int[] nums) {
int n = nums.length, dp[][] = new int[nums.length][nums.length];
for (int i = 0; i < n; i++) dp[i][i] = nums[i];
for (int k = 1; k < n; k++) for (int i = 0; i < n - k; i++) dp[i][i + k] = Math.max(nums[i] - dp[i + 1][i + k], nums[i + k] - dp[i][i + k - 1]);
return dp[0][n - 1] >= 0;
}
}
Python:
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
n, dp = len(nums), nums[:]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1])
return dp[-1] >= 0
