1690. Stone Game VII

MediumArrayMathDynamic ProgrammingGame Theory

Problem Description

In this game, Alice and Bob are playing a turn-based game with an array (row) of stones. Each stone has a certain value associated with it. Alice starts first and at each turn, a player can remove either the leftmost or the rightmost stone. The score for each turn is calculated as the sum of values of the remaining stones in the array. The objective for Alice is to maximize the score difference by the end of the game, while Bob wants to minimize this difference. The final output should be the difference in scores between Alice and Bob if both play optimally. In other words, we are looking for the best strategy for both players such that Alice maximizes and Bob minimizes the end score difference, and we want to know what that difference is.

Intuition

The intuition behind solving this problem lies in recognizing it as a dynamic programming (DP) problem and understanding game theory. Given that both players are playing optimally, we need to decide at each step which choice (taking the leftmost or rightmost stone) will lead to the best possible outcome for the player whose turn it is while considering that the other player will also play optimally.

Since the score that a player gets in their turn depends not just on their immediate decision but also on the remaining array of stones, this gives us a hint that we need a way to remember outcomes for particular situations to avoid redundant calculations. This kind of optimization is where dynamic programming shines.

The solution uses depth-first search (DFS) with memoization (or DP), which essentially remembers ('caches') the results of certain calculations (here, score differences for given i and j where i and j denote the current indices of the stones in the row that players can pick from).

The caching is achieved using the @cache decorator, which means that when the dfs function is called repeatedly with the same i, j arguments, it will not recompute the function but instead retrieve the result from an internal cache.

The 'dfs' function is designed to select the optimal move at each step. It does this by calculating the score difference when removing a stone from the left (denoted by 'a') and from the right (denoted by 'b'), and then choosing the maximum of these two for the player whose turn it is. This ensures that each player's move – whether it's Alice maximizing the score difference or Bob minimizing it – contributes to the overall optimal strategy.

Finally, the precomputed prefix sums (accumulate(stones, initial=0)) help to quickly calculate the sum of the remaining stones with constant time lookups, which significantly improves the performance of the algorithm. The intuition here is to optimize the sum calculation within the row of stones, as this operation is required repeatedly for determining scores.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution to the problem leverages dynamic programming (DP) and depth-first search (DFS) to find the optimal moves for Alice and Bob.

Here's a walk-through of the implementation steps of the solution:

Memoization with @cache: We begin by defining a recursive function dfs(i, j) which accepts two parameters indicating the indexes of the row from which the players can take stones. The @cache decorator is used to store the results of the function calls, ensuring that each unique state is only calculated once, thus reducing the number of repeat computations.
Base Case of Recursion: When the indices i and j cross each other (i > j), it means there are no stones left to be removed, and the function returns 0 as there are no more points to be scored.
Recursive Case – Computing Scores:
- a = s[j + 1] - s[i + 1] - dfs(i + 1, j) calculates the score difference if the leftmost stone is taken. It computes the sum of remaining stones using prefix sums and then subtracts the optimal result of the sub-problem where the leftmost has been removed (we advance i by 1).
- b = s[j] - s[i] - dfs(i, j - 1) does the similar calculation for the rightmost stone.
Choosing the Optimal Move: The function then returns the maximum of these two options, max(a, b). For Alice, this means maximizing the score difference, while for Bob, due to the recursive nature of the algorithm, this means choosing the move that minimally increases Alice's advantage.
Prefix Sums with accumulate: s = list(accumulate(stones, initial=0)) is used to create an array of prefix sums to speed up the calculation of the sum of the remaining stones.
Computing the Answer: The main function then calls dfs(0, len(stones) - 1) to initiate the recursive calls starting from the whole array of stones. The final answer represents the best possible outcome of the difference in scores, assuming both Alice and Bob play optimally.
Clearing the Cache (Optional): dfs.cache_clear() can be called to clear the cache if necessary, but it's optional and doesn't affect the output for this single-case computation.

By employing DP with memoization, the solution ensures that the computation for each sub-array of stones defined by indices i and j is only done once. Coupled with an optimally designed recursive function and the use of prefix sums for rapid summation, this approach considerably reduces the time complexity that would otherwise be exponential due to the overlapping subproblems present in naive recursion.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have an array stones of [3, 9, 1, 2], where each number represents the value of a stone.

Initialize Prefix Sums: Using the accumulate function, we create the prefix sums array s, which becomes [0, 3, 12, 13, 15]. The 0 is an initial value for easier computation.
Invoke dfs(0, 3): We start the depth-first search with the entire array, with i=0 and j=3 (index of the first and last stones).
Determine Score Differences:
- When taking the leftmost (3), dfs(1, 3) is called, resulting in a = s[4] - s[2] - dfs(1, 3) => a = 15 - 12 - dfs(1, 3) => a = 3 - dfs(1, 3).
- When taking the rightmost (2), dfs(0, 2) is called, resulting in b = s[3] - s[1] - dfs(0, 2) => b = 13 - 3 - dfs(0, 2) => b = 10 - dfs(0, 2).

At this point, we need the results of dfs(1, 3) and dfs(0, 2) to continue.

Recursive Calls:
- For dfs(1, 3): Again, we decide between dfs(2, 3) (taking 9) and dfs(1, 2) (taking 2).
  - If we take 9, dfs(2, 3) results in a = s[4] - s[3] - dfs(2, 3) => a = 15 - 13 - dfs(2, 3) => a = 2 - dfs(2, 3).
  - If we take 2, dfs(1, 2) results in b = s[3] - s[2] - dfs(1, 2) => b = 13 - 12 - dfs(1, 2) => b = 1 - dfs(1, 2).
- For dfs(0, 2): This will follow similar steps, evaluating the removal of stones at the positions (0, 2).
Base Case: Eventually, the calls will reach a base case where i > j in which case dfs returns 0.
Memoization: As these calls are made, the results are stored thanks to the @cache decorator, meaning that any repeated calculations for the same state are fetched from cache rather than recomputed.
Determine Best Move at Each Step: dfs function will return the maximum value of the a or b calculated at each step, providing the score difference up to that point.
Trace Back to First Call: The results of the sub-problems build upon each other to provide the result of the initial call dfs(0, 3), which gives the final optimal score difference.

For our case:

We start with the full array: dfs(0, 3)
Then explore taking a stone from the left and right, recursively: dfs(1, 3) and dfs(0, 2)
This process continues, exploring all possibilities, but efficiently with memoization.
We'll get a sequence of decisions that will maximize the difference for Alice if she starts, and minimize it for Bob.

Final Answer: After dfs(0, 3) is fully executed with all its recursive dependencies solved, the result is then the optimal score difference with Alice starting, given that both players play optimally.

Solution Implementation

1from typing import List
2from functools import lru_cache
3from itertools import accumulate
4
5class Solution:
6    def stoneGameVII(self, stones: List[int]) -> int:
7        # Helper function that uses dynamic programming with memoization
8        @lru_cache(maxsize=None)  # Use lru_cache for memoization
9        def dp(low, high):
10            # Base condition: if no stones are left
11            if low > high:
12                return 0
13          
14            # If Alice removes the stone at the low end, the new score is computed
15            # from the remaining pile (low+1 to high) and current total score
16            score_when_remove_low = prefix_sums[high + 1] - prefix_sums[low + 1] - dp(low + 1, high)
17          
18            # If Alice removes the stone at the high end, the new score is computed
19            # from the remaining pile (low to high-1) and current total score
20            score_when_remove_high = prefix_sums[high] - prefix_sums[low] - dp(low, high - 1)
21          
22            # Return the max score Alice can achieve from the current situation
23            return max(score_when_remove_low, score_when_remove_high)
24      
25        # Construct the prefix sums list where prefix_sums[i] is the sum of stones[0] to stones[i-1]
26        prefix_sums = [0] + list(accumulate(stones))
27      
28        # Calculate the maximum score difference Alice can achieve by starting from the full size of the stones pile
29        answer = dp(0, len(stones) - 1)
30      
31        # Clear the cache since it is no longer needed
32        dp.cache_clear()
33      
34        return answer  # Return the answer
35

1class Solution {
2    // Prefix sum array to efficiently calculate the score.
3    private int[] prefixSum;
4    // Memoization table to store results of subproblems.
5    private Integer[][] memo;
6
7    public int stoneGameVII(int[] stones) {
8        int n = stones.length;
9        prefixSum = new int[n + 1];
10        memo = new Integer[n][n];
11      
12        // Compute prefix sums for stones to help calculate the score quickly.
13        for (int i = 0; i < n; ++i) {
14            prefixSum[i + 1] = prefixSum[i] + stones[i];
15        }
16      
17        // Begin the game from the first stone to the last stone.
18        return dfs(0, n - 1);
19    }
20
21    // Recursive function with memoization to compute the maximum score difference.
22    private int dfs(int left, int right) {
23        // Base case: when there are no stones, the score difference is 0.
24        if (left > right) {
25            return 0;
26        }
27      
28        // Check if the result for this subproblem is already computed.
29        if (memo[left][right] != null) {
30            return memo[left][right];
31        }
32      
33        // The score difference if we remove the left-most stone.
34        int scoreRemoveLeft = prefixSum[right + 1] - prefixSum[left + 1] - dfs(left + 1, right);
35        // The score difference if we remove the right-most stone.
36        int scoreRemoveRight = prefixSum[right] - prefixSum[left] - dfs(left, right - 1);
37      
38        // The player chooses the option that maximizes the score difference.
39        // The result of the subproblem is the maximum score that can be achieved.
40        memo[left][right] = Math.max(scoreRemoveLeft, scoreRemoveRight);
41
42        return memo[left][right];
43    }
44}
45

1#include <vector>
2#include <cstring>
3#include <functional>
4using namespace std;
5
6class Solution {
7public:
8    int stoneGameVII(vector<int>& stones) {
9        int n = stones.size();
10        // Define a 2D array f to memorize the results
11        vector<vector<int>> dp(n, vector<int>(n, 0));
12
13        // Define an array to store the prefix sums of the stones
14        vector<int> prefixSum(n + 1, 0);
15        for (int i = 0; i < n; ++i) {
16            prefixSum[i + 1] = prefixSum[i] + stones[i];
17        }
18
19        // Define a recursive lambda function for depth-first search
20        function<int(int, int)> dfs = [&](int left, int right) {
21            // Base case: if the game is over (no stones left), the score is 0.
22            if (left > right) {
23                return 0;
24            }
25            // If we have already computed the result for this interval, return it
26            if (dp[left][right] != 0) {
27                return dp[left][right];
28            }
29            // Calculate score if removing the leftmost stone
30            int scoreIfRemoveLeft = prefixSum[right + 1] - prefixSum[left + 1] - dfs(left + 1, right);
31            // Calculate score if removing the rightmost stone
32            int scoreIfRemoveRight = prefixSum[right] - prefixSum[left] - dfs(left, right - 1);
33
34            // The result for the current interval is the maximum score the current player can achieve
35            dp[left][right] = max(scoreIfRemoveLeft, scoreIfRemoveRight);
36            return dp[left][right];
37        };
38
39        // Start the game from the full range of stones and return the maximum possible score
40        return dfs(0, n - 1);
41    }
42};
43

1function stoneGameVII(stones: number[]): number {
2    const n: number = stones.length;
3    // Define a 2D array dp to memorize the results
4    const dp: number[][] = Array.from({length: n}, () => Array(n).fill(0));
5
6    // Define an array to store the prefix sums of the stones
7    const prefixSum: number[] = Array(n + 1).fill(0);
8    for (let i = 0; i < n; ++i) {
9        prefixSum[i + 1] = prefixSum[i] + stones[i];
10    }
11
12    // Define a recursive lambda function for depth-first search
13    const dfs: (left: number, right: number) => number = (left, right) => {
14        // Base case: if the game is over (no stones left), the score is 0.
15        if (left > right) {
16            return 0;
17        }
18        // If we have already computed the result for this interval, return it
19        if (dp[left][right] !== 0) {
20            return dp[left][right];
21        }
22        // Calculate score if removing the leftmost stone
23        const scoreIfRemoveLeft: number = prefixSum[right + 1] - prefixSum[left + 1] - dfs(left + 1, right);
24        // Calculate score if removing the rightmost stone
25        const scoreIfRemoveRight: number = prefixSum[right] - prefixSum[left] - dfs(left, right - 1);
26
27        // The result for the current interval is the maximum score the current player can achieve
28        dp[left][right] = Math.max(scoreIfRemoveLeft, scoreIfRemoveRight);
29        return dp[left][right];
30    };
31
32    // Start the game from the full range of stones and return the maximum possible score
33    return dfs(0, n - 1);
34}
35

Time and Space Complexity

The time complexity of the provided code can be analyzed as follows:

There are n = j - i + 1 states to compute, where n is the total number of stones.
For each state (i, j), we have two choices: to take the stone from the left or the right.
Caching results of subproblems with memoization reduces repeated calculations such that each pair (i, j) is computed once.
Therefore, there are O(n^2) states due to the combination of starting and ending positions.

Hence, the overall time complexity is O(n^2).

The space complexity analysis is as follows:

Space is used to store the results of subproblems; this uses O(n^2) space due to memoization.
The array s has a space complexity of O(n).

The memoization's space complexity is dominant. Therefore, the overall space complexity is O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know