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

想法

這題可能會想到一個用 DFS 的作法。

但那樣遞迴下去找差會跑到 TLE。

所以我們用動態規劃來處理，因為每多一個元素的情況，前一個的差就會反轉過來。

我們有個二維 DP 陣列代表最佳差。

左下三角代表頭比尾後面，所以我們不會用到。

主對角線則是頭尾位置相同，只有單一元素的情況，所以差也為 0。

我們只需要處理右上三角，增加元素的同時扣除前一個的差。

實作

Javascript

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--) {
        // sum 就是區段的分數總和
        let sum = stones[i];
        for(let j = i + 1; j < n; j++) {
            sum += stones[j];
            
            // 移除第一個的差，多了一個元素，所以把上次的反轉扣除
            let remove_first = sum - stones[i] - dp[i + 1][j];
            // 移除最後一個的差，多了一個元素，所以把上次的反轉扣除
            let remove_last = sum - stones[j] - dp[i][j - 1];
            
            // Alex 必定會選較大的那個
            dp[i][j] = remove_first > remove_last ? remove_first : remove_last;
        }
    }
    
    // 回傳全區段的情形下的差
    return dp[0][n - 1];
};

• leetcode
• problem
• june challenge 2021