Formatted question description: https://leetcode.ca/all/1690.html

# 1690. Stone Game VII (Medium)

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, they can **remove** either the leftmost stone or the rightmost stone from the row and receive points equal to the **sum** of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to **minimize the score's difference**. Alice's goal is to **maximize the difference** in the score.

Given an array of integers `stones`

where `stones[i]`

represents the value of the `i`

stone ^{th}**from the left**, return *the difference in Alice and Bob's score if they both play optimally.*

**Example 1:**

Input:stones = [5,3,1,4,2]Output:6Explanation:- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4]. - Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4]. - Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4]. - Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4]. - Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = []. The score difference is 18 - 12 = 6.

**Example 2:**

Input:stones = [7,90,5,1,100,10,10,2]Output:122

**Constraints:**

`n == stones.length`

`2 <= n <= 1000`

`1 <= stones[i] <= 1000`

**Related Topics**:

Dynamic Programming

**Similar Questions**:

- Stone Game (Medium)
- Stone Game II (Medium)
- Stone Game III (Hard)
- Stone Game IV (Hard)
- Stone Game V (Hard)
- Stone Game VI (Medium)

## Solution 1. Bottom-up DP

Let `dp[i][j]`

be the maximum difference the first player can get if the players play on `A[i..j]`

.

```
dp[i][j] = max(
sum(i + 1, j) - dp[i + 1][j], // if the first player choose `A[i]`
sum(i, j - 1) - dp[i][j - 1] // if the first player choose `A[j]`
)
```

where `sum(i, j)`

is `A[i] + ... + A[j]`

. We can get `sum(i, j)`

using prefix sum array.

**Explanation of the DP formula**

Each player needs to play optimally to get as many points as possible and make the other player get as less as possible. So the game is actually the same for both of them.

After Alice finshes the her first round, ignoring the points Alice made there, the game to Bob is exactly the same as if he is the first player.

So each round on `A[i..j]`

, no matter who plays first, the first player always has two options:

- pick
`A[i]`

, the first player get`sum(i + 1, j)`

points, and we need to deduct the maximum point difference the next player can get in the remaining game, i.e.`dp[i + 1][j]`

- pick
`A[j]`

, the first player get`sum(i, j - 1)`

points, and we need to deduct the maximum point difference the next player can get in the remaining game, i.e.`dp[i][j - 1]`

And the first player simply pick the option more advantageous to him/her.

```
// OJ: https://leetcode.com/contest/weekly-contest-219/problems/stone-game-vii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int stoneGameVII(vector<int>& A) {
int N = A.size();
vector<int> sum(N + 1);
for (int i = 0; i < N; ++i) sum[i + 1] = sum[i] + A[i];
vector<vector<int>> dp(N, vector<int>(N));
for (int len = 2; len <= N; ++len) {
for (int i = 0; i <= N - len; ++i) {
int j = i + len - 1;
dp[i][j] = max(sum[j + 1] - sum[i + 1] - dp[i + 1][j], sum[j] - sum[i] - dp[i][j - 1]);
}
}
return dp[0][N - 1];
}
};
```

Java

```
class Solution {
public int stoneGameVII(int[] stones) {
int length = stones.length;
int[] prefixSums = new int[length];
prefixSums[0] = stones[0];
for (int i = 1; i < length; i++)
prefixSums[i] = prefixSums[i - 1] + stones[i];
int[][] dp = new int[length][length];
for (int i = length - 2; i >= 0; i--) {
for (int j = i + 1; j < length; j++)
dp[i][j] = Math.max(getRangeSum(prefixSums, i + 1, j) - dp[i + 1][j], getRangeSum(prefixSums, i, j - 1) - dp[i][j - 1]);
}
return dp[0][length - 1];
}
public int getRangeSum(int[] prefixSums, int start, int end) {
return start == 0 ? prefixSums[end] : prefixSums[end] - prefixSums[start - 1];
}
}
```