1690. Stone Game VII

---

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 ith stone 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: 6
Explanation: 
- 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

---

解法1

定义一个函数,返回值是双方分数的差值,Bob每次都要找最小的差值, 而Alice找最大的

class Solution {
    public int stoneGameVII(int[] stones) {
        int sum = 0;
        for(int s : stones)
            sum += s;
        return helper(stones, 0, stones.length - 1, true, sum);
    }
    
    private int helper(int[] stones, int left, int right, boolean isAlice, int sum){
        int sl = sum - stones[left], sr = sum - stones[right];
        
        // Alice remove the stone
        if(isAlice){
            if(left == right)
                return sl;
        
            return Math.max(helper(stones, left + 1, right, !isAlice, sl) + sl, helper(stones, left ,right - 1, !isAlice, sr) + sr);
        }
        // Bob remove the stone
        else{
            if(left == right)
                return -sl;
            
            return Math.min(helper(stones, left + 1, right, !isAlice, sl) - sl, helper(stones, left ,right - 1, !isAlice, sr) - sr);
        }
    }
}

---

解法2

解法1中包含了很多的重复运算, 可以用两个二维数组,或者一个三维数组来保存计算结果.

class Solution {
    
    Integer[][][] memo ;
    
    public int stoneGameVII(int[] stones) {
        int len = stones.length;
        // keep tracking the difference
        memo = new Integer[len][len][2];
        
        // the totol scores of remaining stones
        int sum = 0;
        for(int s : stones)
            sum += s;

        
        return helper(stones, 0, stones.length - 1, 1, sum);
    }
    
    private int helper(int[] stones, int left, int right, int isAlice, int sum){
        if(left > right)
            return 0;
        if(memo[left][right][isAlice] != null)
            return memo[left][right][isAlice];
        
        // the sum of removing the left stone
        int sl = sum - stones[left];
        // the sum of removing the right stone
        int sr = sum - stones[right];
        
        // Alice remove the stone
        if(isAlice == 1){
            int scoreLeft = helper(stones, left + 1, right, 1 - isAlice, sl) + sl;
            int scoreRight = helper(stones, left ,right - 1, 1 - isAlice, sr) + sr;
            memo[left][right][isAlice] = Math.max(scoreLeft, scoreRight);
        }
        // Bob remove the stone
        else{
            int scoreLeft = helper(stones, left + 1, right, 1 - isAlice, sl) - sl;
            int scoreRight = helper(stones, left ,right - 1, 1 - isAlice, sr) - sr;
            memo[left][right][isAlice] = Math.min(scoreLeft, scoreRight);
        }
        
        return memo[left][right][isAlice];
    }
}

---

解法3

参考这个URL

[Java] DP with a bit of explanation, O(n^2) time, O(n) space

有一点需要注意,就是为什么可以一直求最大值. 因为其实Alice和Bob的目标都是一样的, 是求得当前情况下自己获得最大分数 (真的吗? 想不清楚,隐隐的觉得不太对,有时间再来琢磨)

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length, prefix[] = new int[n], dp[] = new int[n];

        for (var i = 0; i < n; i ++) {
            prefix[i] = stones[i] + (i > 0 ? prefix[i - 1] : 0);
        }

        for (var i = 0; i < n - 1; i ++) {
            dp[i]= Math.max(stones[i], stones[i + 1]);
        }
        
        for (var l = 2; l < n; l ++) {
            // length of current stone array = l + 1
            for (var i = 0; i < n - l; i ++) {
                dp[i] = Math.max(
                    prefix[i + l - 1] - (i > 0 ? prefix[i - 1] : 0) - dp[i],      // sum(i, i + l - 1)
                    prefix[i + l] - prefix[i] - dp[i + 1]
                );
            }
        }
        
        return dp[0];
    }
}