1872. Stone Game VIII
Description
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:
<li>Choose an integer <code>x > 1</code>, and <strong>remove</strong> the leftmost <code>x</code> stones from the row.</li>
<li>Add the <strong>sum</strong> of the <strong>removed</strong> stones' values to the player's score.</li>
<li>Place a <strong>new stone</strong>, whose value is equal to that sum, on the left side of the row.</li>
The game stops when only one stone is left in the row.
The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.
Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.
Example 1:
Input: stones = [-1,2,-3,4,-5] Output: 5 Explanation: - Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of value 2 on the left. stones = [2,-5]. - Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on the left. stones = [-3]. The difference between their scores is 2 - (-3) = 5.
Example 2:
Input: stones = [7,-6,5,10,5,-2,-6] Output: 13 Explanation: - Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a stone of value 13 on the left. stones = [13]. The difference between their scores is 13 - 0 = 13.
Example 3:
Input: stones = [-10,-12] Output: -22 Explanation: - Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her score and places a stone of value -22 on the left. stones = [-22]. The difference between their scores is (-22) - 0 = -22.
Constraints:
<li><code>n == stones.length</code></li>
<li><code>2 <= n <= 10<sup>5</sup></code></li>
<li><code>-10<sup>4</sup> <= stones[i] <= 10<sup>4</sup></code></li>
Solutions
Solution 1: Prefix Sum + Memoization Search
According to the problem description, each time we take the leftmost $x$ stones, add their sum to our score, and then put a stone with this sum value on the leftmost side, it is equivalent to merging these $x$ stones into a stone with this sum value, and the prefix sum remains unchanged.
We can use a prefix sum array $s$ of length $n$ to represent the prefix sum of the array $stones$, where $s[i]$ represents the sum of the elements $stones[0..i]$.
Next, we design a function $dfs(i)$, which means that we currently take stones from $stones[i:]$, and return the maximum score difference that the current player can get.
The execution process of the function $dfs(i)$ is as follows:
If $i \geq n - 1$, it means that we can only take all the stones at present, so we return $s[n - 1]$.
Otherwise, we can choose to take all the stones from $stones[i + 1:]$, and the score difference obtained is $dfs(i + 1)$; we can also choose to take the stones $stones[:i]$, and the score difference obtained is $s[i] - dfs(i + 1)$. We take the maximum of the two situations, which is the maximum score difference that the current player can get.
Finally, we can get the score difference between Alice and Bob as $dfs(1)$, that is, Alice must start the game by taking stones from $stones[1:]$.
To avoid repeated calculations, we can use memoization search.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $stones$.
Python3
class Solution:
def stoneGameVIII(self, stones: List[int]) -> int:
@cache
def dfs(i: int) -> int:
if i >= len(stones) - 1:
return s[-1]
return max(dfs(i + 1), s[i] - dfs(i + 1))
s = list(accumulate(stones))
return dfs(1)
Java
class Solution {
private Integer[] f;
private int[] s;
private int n;
public int stoneGameVIII(int[] stones) {
n = stones.length;
f = new Integer[n];
for (int i = 1; i < n; ++i) {
stones[i] += stones[i - 1];
}
s = stones;
return dfs(1);
}
private int dfs(int i) {
if (i >= n - 1) {
return s[i];
}
if (f[i] == null) {
f[i] = Math.max(dfs(i + 1), s[i] - dfs(i + 1));
}
return f[i];
}
}
C++
class Solution {
public:
int stoneGameVIII(vector<int>& stones) {
int n = stones.size();
for (int i = 1; i < n; ++i) {
stones[i] += stones[i - 1];
}
int f[n];
memset(f, -1, sizeof(f));
function<int(int)> dfs = [&](int i) -> int {
if (i >= n - 1) {
return stones[i];
}
if (f[i] == -1) {
f[i] = max(dfs(i + 1), stones[i] - dfs(i + 1));
}
return f[i];
};
return dfs(1);
}
};
Go
func stoneGameVIII(stones []int) int {
n := len(stones)
f := make([]int, n)
for i := range f {
f[i] = -1
}
for i := 1; i < n; i++ {
stones[i] += stones[i-1]
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n-1 {
return stones[i]
}
if f[i] == -1 {
f[i] = max(dfs(i+1), stones[i]-dfs(i+1))
}
return f[i]
}
return dfs(1)
}
TypeScript
function stoneGameVIII(stones: number[]): number {
const n = stones.length;
const f: number[] = Array(n).fill(-1);
for (let i = 1; i < n; ++i) {
stones[i] += stones[i - 1];
}
const dfs = (i: number): number => {
if (i >= n - 1) {
return stones[i];
}
if (f[i] === -1) {
f[i] = Math.max(dfs(i + 1), stones[i] - dfs(i + 1));
}
return f[i];
};
return dfs(1);
}
Solution 2: Prefix Sum + Dynamic Programming
We can also use dynamic programming to solve this problem.
Similar to Solution 1, we first use a prefix sum array $s$ of length $n$ to represent the prefix sum of the array $stones$, where $s[i]$ represents the sum of the elements $stones[0..i]$.
We define $f[i]$ to represent the maximum score difference that the current player can get when taking stones from $stones[i:]$.
If the player chooses to take the stones $stones[:i]$, then the score obtained is $s[i]$. At this time, the other player will take stones from $stones[i+1:]$, and the maximum score difference that the other player can get is $f[i+1]$. Therefore, the maximum score difference that the current player can get is $s[i] - f[i+1]$.
If the player chooses to take stones from $stones[i+1:]$, then the maximum score difference obtained is $f[i+1]$.
Therefore, we can get the state transition equation:
$$ f[i] = \max{s[i] - f[i+1], f[i+1]} $$
Finally, we can get the score difference between Alice and Bob as $f[1]$, that is, Alice must start the game by taking stones from $stones[1:]$.
We notice that $f[i]$ is only related to $f[i+1]$, so we only need to use a variable $f$ to represent $f[i]$.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $stones$.
Python3
class Solution:
def stoneGameVIII(self, stones: List[int]) -> int:
s = list(accumulate(stones))
f = s[-1]
for i in range(len(s) - 2, 0, -1):
f = max(f, s[i] - f)
return f
Java
class Solution {
public int stoneGameVIII(int[] stones) {
int n = stones.length;
for (int i = 1; i < n; ++i) {
stones[i] += stones[i - 1];
}
int f = stones[n - 1];
for (int i = n - 2; i > 0; --i) {
f = Math.max(f, stones[i] - f);
}
return f;
}
}
C++
class Solution {
public:
int stoneGameVIII(vector<int>& stones) {
int n = stones.size();
for (int i = 1; i < n; ++i) {
stones[i] += stones[i - 1];
}
int f = stones.back();
for (int i = n - 2; i; --i) {
f = max(f, stones[i] - f);
}
return f;
}
};
TypeScript
function stoneGameVIII(stones: number[]): number {
const n = stones.length;
for (let i = 1; i < n; ++i) {
stones[i] += stones[i - 1];
}
let f = stones[n - 1];
for (let i = n - 2; i; --i) {
f = Math.max(f, stones[i] - f);
}
return f;
}