目标
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 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。说明：
- 1 <= stoneValue.length <= 5 * 10^4
- -1000 <= stoneValue[i] <= 1000
思路
几堆石子排成一排，stoneValue[i] 表示第 i 堆石子的个数。Alice 与 Bob 轮流取石子，Alice 先取，每次可以从剩余的石子堆中取走前 1、2 或者 3 堆石子，直到石子均被取走。返回结束时取走石子最多的玩家姓名，如果相同则返回 Tie。
定义 dp[i] 表示剩余 [i, n - 1] 堆石子，先手与后手所能获得的石子个数之差的最大值。dp[i] = max(sumj - dp[j + 1])，其中 j ∈ [i, min(i + 2, n - 1)]，sumj 表示 [i, j] 的石子堆数量之和。倒序遍历，初始化 dp[n] = 0, dp[n - 1] = stoneValue[n - 1]。
代码
/**
* @date 2026-08-03 15:22
*/
public class StoneGameIII1406 {
public String stoneGameIII(int[] stoneValue) {
int n = stoneValue.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[n] = 0;
dp[n - 1] = stoneValue[n - 1];
for (int i = n - 1; i >= 0; i--) {
int sum = 0;
for (int j = i; j < Math.min(n, i + 3); j++) {
sum += stoneValue[j];
dp[i] = Math.max(dp[i], sum - dp[j + 1]);
}
}
if (dp[0] == 0) {
return "Tie";
}
return dp[0] > 0 ? "Alice" : "Bob";
}
}
性能
