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 * 104-1000 <= stoneValue[i] <= 1000
方法一：记忆化搜索
我们设计一个函数
函数
- 如果
$i \geq n$ ，说明当前没有石子可以拿了，直接返回$0$ 即可； - 否则，我们枚举当前玩家拿走前
$j+1$ 堆石子，其中$j \in {0, 1, 2}$ ，那么另一个玩家在下一轮可以获得的得分差值为$dfs(i + j + 1)$ ，从而当前玩家可以获得的得分差值为$\sum_{k=i}^{i+j} stoneValue[k] - dfs(i + j + 1)$ 。我们要使得当前玩家的得分差值最大，因此可以用$\max$ 函数得到最大得分差值，即：
为了防止重复计算，我们可以使用记忆化搜索。
时间复杂度
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
ans, s = -inf, 0
for j in range(3):
if i + j >= n:
break
s += stoneValue[i + j]
ans = max(ans, s - dfs(i + j + 1))
return ans
n = len(stoneValue)
ans = dfs(0)
if ans == 0:
return 'Tie'
return 'Alice' if ans > 0 else 'Bob'class Solution {
private int[] stoneValue;
private Integer[] f;
private int n;
public String stoneGameIII(int[] stoneValue) {
n = stoneValue.length;
f = new Integer[n];
this.stoneValue = stoneValue;
int ans = dfs(0);
if (ans == 0) {
return "Tie";
}
return ans > 0 ? "Alice" : "Bob";
}
private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] != null) {
return f[i];
}
int ans = -(1 << 30);
int s = 0;
for (int j = 0; j < 3 && i + j < n; ++j) {
s += stoneValue[i + j];
ans = Math.max(ans, s - dfs(i + j + 1));
}
return f[i] = ans;
}
}class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
int f[n];
memset(f, 0x3f, sizeof(f));
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) {
return 0;
}
if (f[i] != 0x3f3f3f3f) {
return f[i];
}
int ans = -(1 << 30), s = 0;
for (int j = 0; j < 3 && i + j < n; ++j) {
s += stoneValue[i + j];
ans = max(ans, s - dfs(i + j + 1));
}
return f[i] = ans;
};
int ans = dfs(0);
if (ans == 0) {
return "Tie";
}
return ans > 0 ? "Alice" : "Bob";
}
};func stoneGameIII(stoneValue []int) string {
n := len(stoneValue)
f := make([]int, n)
const inf = 1 << 30
for i := range f {
f[i] = inf
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != inf {
return f[i]
}
ans, s := -(1 << 30), 0
for j := 0; j < 3 && i+j < n; j++ {
s += stoneValue[i+j]
ans = max(ans, s-dfs(i+j+1))
}
f[i] = ans
return ans
}
ans := dfs(0)
if ans == 0 {
return "Tie"
}
if ans > 0 {
return "Alice"
}
return "Bob"
}
func max(a, b int) int {
if a > b {
return a
}
return b
}function stoneGameIII(stoneValue: number[]): string {
const n = stoneValue.length;
const inf = 1 << 30;
const f: number[] = new Array(n).fill(inf);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i] !== inf) {
return f[i];
}
let ans = -inf;
let s = 0;
for (let j = 0; j < 3 && i + j < n; ++j) {
s += stoneValue[i + j];
ans = Math.max(ans, s - dfs(i + j + 1));
}
return (f[i] = ans);
};
const ans = dfs(0);
if (ans === 0) {
return 'Tie';
}
return ans > 0 ? 'Alice' : 'Bob';
}