英文原文
Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2 or 3 stones from the first remaining stones in the row.
The score of each player is the sum of values of the stones taken. The score of each player is 0 initially.
The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.
Assume Alice and Bob play optimally.
Return "Alice" if Alice will win, "Bob" if Bob will win or "Tie" if they end the game with the same score.
Example 1:
Input: values = [1,2,3,7] Output: "Bob" Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.
Example 2:
Input: values = [1,2,3,-9] Output: "Alice" Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score. If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. The next move Alice will take the pile with value = -9 and lose. If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. The next move Alice will take the pile with value = -9 and also lose. Remember that both play optimally so here Alice will choose the scenario that makes her win.
Example 3:
Input: values = [1,2,3,6] Output: "Tie" Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.
Example 4:
Input: values = [1,2,3,-1,-2,-3,7] Output: "Alice"
Example 5:
Input: values = [-1,-2,-3] Output: "Tie"
Constraints:
1 <= values.length <= 50000-1000 <= values[i] <= 1000
中文题目
Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。
Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。
假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，平局（分数相同）返回 "Tie" 。
示例 1：
输入：values = [1,2,3,7] 输出："Bob" 解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。
示例 2：
输入：values = [1,2,3,-9] 输出："Alice" 解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。 如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。 如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。 注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。
示例 3：
输入：values = [1,2,3,6] 输出："Tie" 解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。
示例 4：
输入：values = [1,2,3,-1,-2,-3,7] 输出："Alice"
示例 5：
输入：values = [-1,-2,-3] 输出："Tie"
提示：
1 <= values.length <= 50000-1000 <= values[i] <= 1000
通过代码
高赞题解
容易让人魔怔的零和博弈！Σ(っ °Д °;)っ
为了便于理解，我们假设下标从 1 开始。
设 dp[i] 代表在 [i…n] 上，先手采取最优策略的得分。注意：这里的先手并不是特指Alice或Bob，而是指在 [i…n] 这个局面下先选择的人。
因为必须拿 1 或 2 或 3 堆，所以 dp[n] = stoneValue[n]，即只有一堆时，先手必须拿走，无论该数字的正负。
当 i ∈ [1, n-1] 时，先手有多种策略可选，但先手一定会选择让后手得分最少的策略。因为是零和博弈，总数就那些，对手得分少了，自己得分就高。
根据题意，先手共有三种策略 j = 1 或 j = 2 或 j = 3，对应的，在后手的回合，后手会面临三种局面，即从 [i+1, n]，[i+2, n]，[i+3, n] 选取最优解。
当然，后手虽然无法选择面临的局面，但他可以选择每种局面中的最优策略。
而先手虽然无法改变后手的策略选择，但可以决定后手面临的局面，先手必然让后手面临三种局面中得分最少的局面！！
Σ(っ °Д °;)っ 品，细品，品完这两句再看下面！
在局面 [i,n] 中，先手选择一块时，自己的最高得分为：
A = stoneValue[i] + sum(i+1, n) - dp[i+1]
先手选择两块时，自己的最高得分为：
B = stoneValue[i, i+1]+ sum(i+2, n) - dp[i+2]
先手选择两块时，自己的最高得分为：
C = stoneValue[i, i+1,i+2]+ sum(i+3, n) - dp[i+3]
腹黑如先手，肯定会选择得分最大的策略！
再细品一下状态转移方程：当先手选完 j 堆石头后，游戏进入到下一回合！先手变后手，后手变先手! 此时的先手依然会选择最优策略即 dp[i+j]，对于上一局的先手来说，他只能获的剩下得部分，即 sum(i+j, n) - dp[i+j]。
品完上代码
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int dp[50003] = {0};
int sum = 0;
for(int n = stoneValue.size(), i = n-1; i >= 0; i--) {
dp[i] = -0x7FFFFFFE;
sum += stoneValue[i];
for(int j = 1; j <= 3; j++) {
dp[i] = max(dp[i], sum - dp[i+j]);
}
}
if(sum - dp[0] == dp[0]) {
return "Tie";
} else if(sum - dp[0] > dp[0]) {
return "Bob";
}
return "Alice";
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 5069 | 8919 | 56.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
