1872. Stone Game VIII

Posted on Edited on In Words count: 2.2k Reading time ≈ 2 mins.

1872. Stone Game VIII

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones' values to the player's score.
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 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:

n == stones.length
2 <= n <= 105
-104 <= stones[i] <= 104

难度 : Hard

思路

DP
首先计算每个位置 i, sum[0,i]
然后从最后的位置向前扫描找到alice得分最大的位置
时间复杂度 : O(N)

1
2
3
4
5
6
7
8
9
10
11

状态转移方程
dp[i] = sum(S[0:i]) - max(dp[i+1], dp[i+2],...dp[n-1])
可以从1开始扫描到n-1,这样会有很多重复计算时间复杂度是O(N^2)
可以从后面向前扫描, 这样时间复杂度到O(N)

ans =  dp[n-1]
dp[n-2] = sum(S[0,n-2]) - dp[n-1] = sum(S[0,n-2]) - ans
# update ans
ans = Math.max(dp[n-2], ans) 
...

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] sum = new int[n];
        sum[0] = stones[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i-1] + stones[i ];
        }
        
        int ans = sum[n - 1];
        for (int i = n - 2; i >= 1; i--) {
            ans = Math.max(ans ,sum[i] - ans);
        }
        return ans;
    }
}