1406. Stone Game III

Approach 1: Top-down

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

C++JavaPython

class Solution {
 public:
  string stoneGameIII(vector<int>& stoneValue) {
    // dp[i] := max "relative score" Alice can make w/ stoneValue[i:]
    dp.resize(stoneValue.size(), INT_MIN);

    const int score = stoneGameIII(stoneValue, 0);
    return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
  }

 private:
  vector<int> dp;

  int stoneGameIII(const vector<int>& stoneValue, int i) {
    if (i == stoneValue.size())
      return 0;
    if (dp[i] > INT_MIN)
      return dp[i];

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

    return dp[i];
  };
};

class Solution {
  public String stoneGameIII(int[] stoneValue) {
    // dp[i] := max "relative score" Alice can make w/ stoneValue[i:]
    dp = new int[stoneValue.length];
    Arrays.fill(dp, Integer.MIN_VALUE);

    final int score = stoneGameIII(stoneValue, 0);
    return score > 0 ? "Alice" : score < 0 ? "Bob" : "Tie";
  }

  private int[] dp;

  private int stoneGameIII(int[] stoneValue, int i) {
    if (i == stoneValue.length)
      return 0;
    if (dp[i] > Integer.MIN_VALUE)
      return dp[i];

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

    return dp[i];
  };
}

class Solution:
  def stoneGameIII(self, stoneValue: List[int]) -> str:
    # Max "relative score" Alice can make w/ stoneValue[i:]
    @functools.lru_cache(None)
    def dp(i: int) -> int:
      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] := max "relative score" Alice can make w/ stoneValue[i:]
    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] := max "relative score" Alice can make w/ stoneValue[i:]
    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] := max "relative score" Alice can make w/ stoneValue[i:]
    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'