1690. Stone Game VII

Problem

Tags: Array, Math, Dynamic Programming, Game Theory

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^th 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

Code

C

// 1690. Stone Game VII (8/24/53956)
// Runtime: 52 ms (94.28%) Memory: 10.40 MB (60.00%) 

int stoneGameVII(int stones[], int stonesSize){
    // dp[a][b] 代表石頭第一個位置是 a 最後一個位置是 b 的差
    int dp[stonesSize][stonesSize];
    memset(dp, 0, sizeof(dp));
    
    for(int i = stonesSize - 1; i >= 0; i--) {
        // sum 就是區段的分數總和
        int sum = stones[i];
        for(int j = i + 1; j < stonesSize; j++) {
            sum += stones[j];
            
            // 移除第一個的差，多了一個元素，所以把上次的反轉扣除
            int remove_first = sum - stones[i] - dp[i + 1][j];
            // 移除最後一個的差，多了一個元素，所以把上次的反轉扣除
            int remove_last = sum - stones[j] - dp[i][j - 1];
            
            // Alex 必定會選較大的那個
            dp[i][j] = remove_first > remove_last ? remove_first : remove_last;
        }
    }
    
    // 回傳全區段的情形下的差
    return dp[0][stonesSize - 1];
}

JS

// 1690. Stone Game VII (6/20/53413)
// Runtime: 592 ms (35.29%) Memory: 64.59 MB (76.47%) 

/**
 * @param {number[]} stones
 * @return {number}
 */
var stoneGameVII = function(stones) {
    const n = stones.length;
    // dp[a][b] 代表石頭第一個位置是 a 最後一個位置是 b 的差
    let dp = Array.from(new Array(n), () => new Array(n).fill(0));
    
    for(let i = n - 1; i >= 0; i--) {
        let sum = 0;
        for(let j = i; j < n; j++) {
            sum += stones[j];
            
            if(i === j) continue;
            
            let remove_first = sum - stones[i] - dp[i + 1][j];
            let remove_last = sum - stones[j] - dp[i][j - 1];
            
            dp[i][j] = remove_first > remove_last ? remove_first : remove_last;
        }
    }
    
    console.log(dp)
    return dp[0][n - 1];
};

# 1690. Stone Game VII

# Problem

# Code

# C

# JS

1690. Stone Game VII

Problem

Code

C

JS