Skip to content

1690. Stone Game VII

SourceWeekly Contest 219 Q3DifficultyMediumRating1951

Description

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

Solutions

Thinking

Each turn removes one end and scores the sum of what remains. The first-player minus second-player gap on an interval is a memoized game: \(dfs(i,j)\) is the current player's advantage.

Prefix sums \(s\) give the score after dropping the left or right end; take the larger of \(s[j+1]-s[i+1]-dfs(i+1,j)\) and \(s[j]-s[i]-dfs(i,j-1)\).

First, we preprocess to get the prefix sum array \(s\), where \(s[i]\) represents the total sum of the first \(i\) stones.

Next, we design a function \(dfs(i, j)\), which represents the score difference between the first and second players when the remaining stones are \(stones[i], stones[i + 1], \dots, stones[j]\). The answer is \(dfs(0, n - 1)\).

The calculation process of the function \(dfs(i, j)\) is as follows:

  • If \(i > j\), it means there are no stones currently, so return \(0\);
  • Otherwise, the first player has two choices, which are to remove \(stones[i]\) or \(stones[j]\), and then calculate the score difference, i.e., \(a = s[j + 1] - s[i + 1] - dfs(i + 1, j)\) and \(b = s[j] - s[i] - dfs(i, j - 1)\). We take the larger of the two as the return value of \(dfs(i, j)\).

During the process, we use memorization search, i.e., use an array \(f\) to record the return value of the function \(dfs(i, j)\), to avoid repeated calculations.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Here, \(n\) is the number of stones.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            a = s[j + 1] - s[i + 1] - dfs(i + 1, j)
            b = s[j] - s[i] - dfs(i, j - 1)
            return max(a, b)

        s = list(accumulate(stones, initial=0))
        ans = dfs(0, len(stones) - 1)
        dfs.cache_clear()
        return ans

 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
class Solution {
    private int[] s;
    private Integer[][] f;

    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        s = new int[n + 1];
        f = new Integer[n][n];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }
        return dfs(0, n - 1);
    }

    private int dfs(int i, int j) {
        if (i > j) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        int a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
        int b = s[j] - s[i] - dfs(i, j - 1);
        return f[i][j] = Math.max(a, b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int>> f(n, vector<int>(n));
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i > j) {
                return 0;
            }
            if (f[i][j]) {
                return f[i][j];
            }
            int a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
            int b = s[j] - s[i] - dfs(i, j - 1);
            return f[i][j] = max(a, b);
        };
        return dfs(0, n - 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func stoneGameVII(stones []int) int {
    n := len(stones)
    s := make([]int, n+1)
    f := make([][]int, n)
    for i, x := range stones {
        s[i+1] = s[i] + x
        f[i] = make([]int, n)
    }
    var dfs func(int, int) int
    dfs = func(i, j int) int {
        if i > j {
            return 0
        }
        if f[i][j] != 0 {
            return f[i][j]
        }
        a := s[j+1] - s[i+1] - dfs(i+1, j)
        b := s[j] - s[i] - dfs(i, j-1)
        f[i][j] = max(a, b)
        return f[i][j]
    }
    return dfs(0, n-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function stoneGameVII(stones: number[]): number {
    const n = stones.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + stones[i];
    }
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    const dfs = (i: number, j: number): number => {
        if (i > j) {
            return 0;
        }
        if (f[i][j]) {
            return f[i][j];
        }
        const a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
        const b = s[j] - s[i] - dfs(i, j - 1);
        return (f[i][j] = Math.max(a, b));
    };
    return dfs(0, n - 1);
}

Solution 2: Dynamic Programming

Thinking

Solution 1 already fills this interval with decreasing \(i\) and increasing \(j\). The \(f[i][j]\) below is that same table.

Solution 1 already fills this transition with decreasing \(i\) and increasing \(j\). Define \(f[i][j]\) as the score difference between the first and second players when the remaining stones are \(stones[i], stones[i + 1], \dots, stones[j]\). Therefore, the answer is \(f[0][n - 1]\).

The state transition equation is as follows:

\[ f[i][j] = \max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1]) \]

When calculating \(f[i][j]\), we need to ensure that \(f[i + 1][j]\) and \(f[i][j - 1]\) have been calculated. Therefore, we need to enumerate \(i\) in descending order and \(j\) in ascending order.

Finally, the answer is \(f[0][n - 1]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Here, \(n\) is the number of stones.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        s = list(accumulate(stones, initial=0))
        n = len(stones)
        f = [[0] * n for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                a = s[j + 1] - s[i + 1] - f[i + 1][j]
                b = s[j] - s[i] - f[i][j - 1]
                f[i][j] = max(a, b)
        return f[0][-1]

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                int a = s[j + 1] - s[i + 1] - f[i + 1][j];
                int b = s[j] - s[i] - f[i][j - 1];
                f[i][j] = max(a, b);
            }
        }
        return f[0][n - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func stoneGameVII(stones []int) int {
    n := len(stones)
    s := make([]int, n+1)
    for i, x := range stones {
        s[i+1] = s[i] + x
    }
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            f[i][j] = max(s[j+1]-s[i+1]-f[i+1][j], s[j]-s[i]-f[i][j-1])
        }
    }
    return f[0][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function stoneGameVII(stones: number[]): number {
    const n = stones.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + stones[i];
    }
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = n - 2; ~i; --i) {
        for (let j = i + 1; j < n; ++j) {
            f[i][j] = Math.max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1]);
        }
    }
    return f[0][n - 1];
}

Solution 3: Dynamic Programming

Thinking

Enumerating both players' choices is exponential. There can be \(1000\) stones, and the branch that removes the left stone first always advances the left endpoint, so the search has depth \(n\). The current player's advantage on \([i,j]\) depends only on shorter intervals. Let \(f[i][j]\) store that difference, with a single stone worth \(0\), and fill decreasing \(i\) and increasing \(j\): removing the left end scores \(s[j+1]-s[i+1]-f[i+1][j]\), removing the right end scores \(s[j]-s[i]-f[i][j-1]\), and the state keeps the larger one.

Precompute the prefix sums \(s\), where \(s[i]\) is the sum of the first \(i\) stones. Let \(f[i][j]\) be the score difference between the current player and the opponent on \(stones[i], stones[i + 1], \dots, stones[j]\). A single stone has difference \(0\). For \(i\) from \(n-2\) down to \(0\), and for each \(i\) with \(j\) from \(i+1\) to \(n-1\), the shorter states \(f[i+1][j]\) and \(f[i][j-1]\) are already known. Removing the left stone scores \(s[j+1]-s[i+1]-f[i+1][j]\), and removing the right stone scores \(s[j]-s[i]-f[i][j-1]\). \(f[i][j]\) is the larger of the two. The answer is \(f[0][n-1]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Here, \(n\) is the number of stones.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        s = list(accumulate(stones, initial=0))
        n = len(stones)
        f = [[0] * n for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                a = s[j + 1] - s[i + 1] - f[i + 1][j]
                b = s[j] - s[i] - f[i][j - 1]
                f[i][j] = max(a, b)
        return f[0][-1]

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                int a = s[j + 1] - s[i + 1] - f[i + 1][j];
                int b = s[j] - s[i] - f[i][j - 1];
                f[i][j] = max(a, b);
            }
        }
        return f[0][n - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func stoneGameVII(stones []int) int {
    n := len(stones)
    s := make([]int, n+1)
    for i, x := range stones {
        s[i+1] = s[i] + x
    }
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            f[i][j] = max(s[j+1]-s[i+1]-f[i+1][j], s[j]-s[i]-f[i][j-1])
        }
    }
    return f[0][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function stoneGameVII(stones: number[]): number {
    const n = stones.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + stones[i];
    }
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = n - 2; ~i; --i) {
        for (let j = i + 1; j < n; ++j) {
            f[i][j] = Math.max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1]);
        }
    }
    return f[0][n - 1];
}

Comments