1872. Stone Game VIII

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:

1. Choose an integer x > 1, and remove the leftmost x stones from the row.
2. Add the sum of the removed stones' values to the player's score.
3. Place a new stone, whose value is equal to that sum, on the left side of the row.

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 i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example: 1

Input: [-1,2,-3,4,-5]

Output: 5

Example: 2

Input: [7,-6,5,10,5,-2,-6]

Output: 13

Example: 3

Input: [-10,-12]

Output: -22

Constraints:

• n == stones.length
• 2 <= n <= 10 ^ 5
• -10 ^ 4 <= stones[i] <= 10 ^ 4

Important observation:

• You are not allowed to pick only one stone. Also after picking up a some stones, the score is added to particular player's current score and finally the a stone whose score equals the sum amount of chosen stones is placed at the beginning.
• For eg : if we have [1, 2, 3, 4, 5] and we take first 3 stones, then the array after this turn will be [6, 4, 5]. After this if you choose 2 stones the arrays becomes [10, 5].
• From the above example you can see clearly that we are only adding prefix sums upto i elements to Alice's or Bob's scores.
• If the above observation does not become clear, try making some random array and try drawing it and solving it on a paper.

Conclusions from the above observation:

Based on the above observation we can have 2 ways for each i :

• Either we will take sum upto i^th element and add it to current players score and give the turn over to other player.
• Or we will continue to the next element by not changing the turn.

The above ways will become clearer through the provided code.

Some base cases:

• You should start by taking two stones in the beginning. This means that your final score will be dp[1] instead of dp[0] (because we must take more than one element always).

Naive implementation using only recursion (will give TLE): class Solution { public int stoneGameVIII(int[] stones) { int n = stones.length; for(int i = 1; i < n; i++) stones[i] += stones[i - 1]; // starting from index 1 // so that minimum 2 stones be selected even from the beginning return recur(1, 0, stones); } int recur(int idx, int turn, int[] prefix) { int curScore = prefix[idx]; // if we have reached the end of array // return that value as positive or negative score // based on user's turn if(idx == prefix.length - 1) { return turn == 0 ? curScore : -curScore; } if(turn % 2 == 0) { // this is Alice's turn // her goal is to maximize the difference // so we are taking max here // condition 1 : recur(idx + 1, turn) means we will continue to next index by ignoring the current sum and keeping the turn with Alice. // condition 2 : curScore + recur(idx + 1, turn ^ 1) means we will take sum upto ith index which is curScore // and add it to Alice's score and then handover the turn to Bob from index (i + 1). // turn ^ 1 means we are changing turn from 0 to 1. return Math.max(recur(idx + 1, turn, prefix), curScore + recur(idx + 1, turn ^ 1, prefix)); } else { // this is Bob's turn // her goal is to minimize the difference // so we are taking min here // condition 1 : recur(idx + 1, turn) means we will continue to next index by ignoring the current sum and keeping the turn with Bob. // condition 2 : -curScore + recur(idx + 1, turn ^ 1) means we will take sum upto ith index which is -curScore // and add it to Bobs's score and then handover the turn to Alice from index (i + 1). // Here we are taking curScore as -curScore because we have to calculate the difference as (Alice's score - Bob's score). // So we add Alice's score and negate Bob's score. // turn ^ 1 means we are changing turn from 0 to 1 return Math.min(recur(idx + 1, turn, prefix), -curScore + recur(idx + 1, turn ^ 1, prefix)); } } }

Changing TLE to Accepted (Using Caching):

• Now we can see clearly that many subproblems are solved multiple times.
• This results into TLE.
• So we will store the results in an array based on the functions index and turn values.
• So we won't be computing the results for each subproblem over and over again.

Full Code (Java): class Solution { Integer[][] dp; public int stoneGameVIII(int[] stones) { int n = stones.length; for(int i = 1; i < n; i++) stones[i] += stones[i - 1]; dp = new Integer[n][2]; return recur(1, 0, stones); } int recur(int idx, int turn, int[] prefix) { // checking if we have already computed the result for current subproblem // if yes, we will return the answer directly without further computations // if no, we will compute the answer and store it as given below if(dp[idx][turn] != null) return dp[idx][turn]; int curScore = prefix[idx]; if(idx == prefix.length - 1) { return turn == 0 ? curScore : -curScore; } if(turn % 2 == 0) { // storing the result for current subproblem in DP array dp[idx][turn] = Math.max(recur(idx + 1, turn, prefix), curScore + recur(idx + 1, turn ^ 1, prefix)); } else { // storing the result for current subproblem in DP array dp[idx][turn] = Math.min(recur(idx + 1, turn, prefix), -curScore + recur(idx + 1, turn ^ 1, prefix)); } return dp[idx][turn]; } }