class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
}
};
1406. 石子游戏 III
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原站题解
python3 解法, 执行用时: 592 ms, 内存消耗: 22.7 MB, 提交时间: 2023-08-18 11:42:52
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
suffix_sum = [0] * (n - 1) + [stoneValue[-1]]
for i in range(n - 2, -1, -1):
suffix_sum[i] = suffix_sum[i + 1] + stoneValue[i]
# 边界情况，当没有石子时，分数为 0
# 为了代码的可读性，显式声明
f = [0] * n + [0]
for i in range(n - 1, -1, -1):
f[i] = suffix_sum[i] - min(f[i+1:i+4])
total = sum(stoneValue)
if f[0] * 2 == total:
return "Tie"
else:
return "Alice" if f[0] * 2 > total else "Bob"
java 解法, 执行用时: 10 ms, 内存消耗: 53.8 MB, 提交时间: 2023-08-18 11:42:03
class Solution {
public String stoneGameIII(int[] stoneValue) {
int n = stoneValue.length;
int[] f = new int[n + 1];
Arrays.fill(f, Integer.MIN_VALUE);
// 边界情况，当没有石子时，分数为 0
f[n] = 0;
for (int i = n - 1; i >= 0; --i) {
int pre = 0;
for (int j = i + 1; j <= i + 3 && j <= n; ++j) {
pre += stoneValue[j - 1];
f[i] = Math.max(f[i], pre - f[j]);
}
}
if (f[0] == 0) {
return "Tie";
} else {
return f[0] > 0 ? "Alice" : "Bob";
}
}
}
python3 解法, 执行用时: 1132 ms, 内存消耗: 20 MB, 提交时间: 2023-08-18 11:41:52
'''
f[i] 表示还剩下第 i,i+1,⋯ ,n−1 堆石子时，当前玩家比下一位玩家最多能多拿到的石子数目
（注意此时依旧是在剩下的石子中定义的）
'''
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
# 边界情况，当没有石子时，分数为 0
f = [-10**9] * n + [0]
for i in range(n - 1, -1, -1):
pre = 0
for j in range(i + 1, min(i + 3, n) + 1):
pre += stoneValue[j - 1]
f[i] = max(f[i], pre - f[j])
if f[0] == 0:
return "Tie"
else:
return "Alice" if f[0] > 0 else "Bob"