Sponsored
Sponsored
This approach uses dynamic programming along with pre-computed prefix sums to efficiently calculate the score differences.
We maintain a 2D DP table where dp[i][j] represents the maximum score difference the current player can achieve over the other player from index i to j. The prefix sums help in computing the sum of the stones between any two indices in constant time, which we require to decide which stone to remove to maximize the score difference.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
1var stoneGameVII = function(stones) {
2 const n = stones.length;
3 const prefixSum = Array(n + 1).fill(0);
4 for (let i = 0; i < n; i++)
5 prefixSum[i + 1] = prefixSum[i] + stones[i];
6 const dp = Array.from({ length: n }, () => Array(n).fill(0));
7
8 for (let length = 2; length <= n; length++) {
9 for (let i = 0; i <= n - length; i++) {
10 const j = i + length - 1;
11 const scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
12 const scoreRemoveRight = prefixSum[j] - prefixSum[i];
13 dp[i][j] = Math.max(scoreRemoveLeft - dp[i + 1][j], scoreRemoveRight - dp[i][j - 1]);
14 }
15 }
16 return dp[0][n - 1];
17};
18In JavaScript, arrays and loops are utilized to build prefix sums and populate the DP table, resulting in optimized calculations of score differences as the process iteratively refines available scores at each round of stone removal.
This approach leverages recursive backtracking with memoization to explore all possible game states and store previously computed results to prevent redundant calculations. Unlike the iterative DP approach, this recursive strategy keeps track of outcomes by diving directly into decision trees, thus exposing base-level game decisions before accumulating overall results with stored solutions.
Time Complexity: O(n^2) (with memoization)
Space Complexity: O(n^2)
1
The JavaScript version embodies a recursive procedure empowered by memoization. This optimization demonstrably maximizes performance by bypassing revisits, caching previous outcomes, and thereby enhancing computational efficiency through cached results.