Question

1406. 石子游戏 III

English Version

题目描述

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

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i)$，表示当前玩家在 $[i, n)$ 范围内进行游戏时，可以获得的最大得分差值。如果 $dfs(0) \gt 0$，则表示先手玩家 Alice 可以获胜；如果 $dfs(0) \lt 0$，则表示后手玩家 Bob 可以获胜；否则，表示两人打成平局。

函数 $dfs(i)$ 的执行逻辑如下：

• 如果 $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$ 函数得到最大得分差值，即：

$$ dfs(i) = \max_{j \in {0, 1, 2}} \left{\sum_{k=i}^{i+j} stoneValue[k] - dfs(i + j + 1)\right} $$

为了防止重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是石子的堆数。

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"
}

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';
}