Skip to content

1872. Stone Game VIII 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int stoneGameVIII(vector<int>& stones) {
    const int n = stones.size();
    vector<int> prefix(n);
    // dp[i] := max score diff the current player can get when the game starts
    // At i, i.e., stones[0..i] are merged whose value is prefix[i]
    vector<int> dp(n, INT_MIN);

    partial_sum(begin(stones), end(stones), begin(prefix));

    // Must take all when there're only two stones left
    dp[n - 2] = prefix.back();

    for (int i = n - 3; i >= 0; --i)
      dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1]);

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int stoneGameVIII(int[] stones) {
    final int n = stones.length;
    int[] prefix = stones.clone();
    // dp[i] := max score diff the current player can get when the game starts
    // At i, i.e., stones[0..i] are merged whose value is prefix[i]
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MIN_VALUE);

    for (int i = 1; i < prefix.length; ++i)
      prefix[i] += prefix[i - 1];

    // Must take all when there're only two stones left
    dp[n - 2] = prefix[n - 1];

    for (int i = n - 3; i >= 0; --i)
      dp[i] = Math.max(dp[i + 1], prefix[i + 1] - dp[i + 1]);

    return dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def stoneGameVIII(self, stones: List[int]) -> int:
    n = len(stones)
    prefix = list(itertools.accumulate(stones))
    # dp[i] := max score diff the current player can get when the game starts
    # At i, i.e., stones[0..i] are merged whose value is prefix[i]
    dp = [-math.inf] * n

    # Must take all when there're only two stones left
    dp[n - 2] = prefix[-1]

    for i in reversed(range(n - 2)):
      dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1])

    return dp[0]