1406. Stone Game III

Approach 1: Top-down

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string stoneGameIII(vector<int>& stoneValue) {
    vector<int> mem(stoneValue.size(), INT_MIN);
    const int score = stoneGameIII(stoneValue, 0, mem);
    return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
  }

 private:
  // Returns the maximum relative score Alice can make from stoneValue[i..n).
  int stoneGameIII(const vector<int>& stoneValue, int i, vector<int>& mem) {
    if (i == stoneValue.size())
      return 0;
    if (mem[i] > INT_MIN)
      return mem[i];

    int sum = 0;
    for (int j = i; j < i + 3 && j < stoneValue.size(); ++j) {
      sum += stoneValue[j];
      mem[i] = max(mem[i], sum - stoneGameIII(stoneValue, j + 1, mem));
    }

    return mem[i];
  };
};

class Solution {
  public String stoneGameIII(int[] stoneValue) {
    int[] mem = new int[stoneValue.length];
    Arrays.fill(mem, Integer.MIN_VALUE);
    final int score = stoneGameIII(stoneValue, 0, mem);
    return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
  }

  // Returns the maximum relative score Alice can make from stoneValue[i..n).
  private int stoneGameIII(int[] stoneValue, int i, int[] mem) {
    if (i == stoneValue.length)
      return 0;
    if (mem[i] > Integer.MIN_VALUE)
      return mem[i];

    int sum = 0;
    for (int j = i; j < i + 3 && j < stoneValue.length; ++j) {
      sum += stoneValue[j];
      mem[i] = Math.max(mem[i], sum - stoneGameIII(stoneValue, j + 1, mem));
    }

    return mem[i];
  };
}

class Solution:
  def stoneGameIII(self, stoneValue: list[int]) -> str:
    @functools.lru_cache(None)
    def dp(i: int) -> int:
      """
      Returns the maximum relative score Alice can make with stoneValue[i..n).
      """
      if i == len(stoneValue):
        return 0

      res = -math.inf
      summ = 0

      for j in range(i, i + 3):
        if j == len(stoneValue):
          break
        summ += stoneValue[j]
        res = max(res, summ - dp(j + 1))

      return res

    score = dp(0)
    if score == 0:
      return 'Tie'
    return 'Alice' if score > 0 else 'Bob'

Approach 2: Bottom-up

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string stoneGameIII(vector<int>& stoneValue) {
    const int n = stoneValue.size();
    // dp[i] := the maximum relative score Alice can make with stoneValue[i..n)
    vector<int> dp(n + 1, INT_MIN / 2);
    dp.back() = 0;

    for (int i = n - 1; i >= 0; --i) {
      int sum = 0;
      for (int j = i; j < i + 3 && j < n; ++j) {
        sum += stoneValue[j];
        dp[i] = max(dp[i], sum - dp[j + 1]);
      }
    }

    const int score = dp[0];
    return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
  }
};

class Solution {
  public String stoneGameIII(int[] stoneValue) {
    final int n = stoneValue.length;
    // dp[i] := the maximum relative score Alice can make with stoneValue[i..n)
    int[] dp = new int[n + 1];
    Arrays.fill(dp, 0, n, Integer.MIN_VALUE / 2);

    for (int i = n - 1; i >= 0; --i) {
      int sum = 0;
      for (int j = i; j < i + 3 && j < n; ++j) {
        sum += stoneValue[j];
        dp[i] = Math.max(dp[i], sum - dp[j + 1]);
      }
    }

    final int score = dp[0];
    return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
  }
}

class Solution:
  def stoneGameIII(self, stoneValue: list[int]) -> str:
    n = len(stoneValue)
    # dp[i] := the maximum relative score Alice can make with stoneValue[i..n)
    dp = [-math.inf] * n + [0]

    for i in reversed(range(n)):
      summ = 0
      for j in range(i, i + 3):
        if j == n:
          break
        summ += stoneValue[j]
        dp[i] = max(dp[i], summ - dp[j + 1])

    score = dp[0]
    if score == 0:
      return 'Tie'
    return 'Alice' if score > 0 else 'Bob'