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)
1using System;
2
3public class Solution {
4 public int StoneGameVII(int[] stones) {
5 int n = stones.Length;
6 int[] prefixSum = new int[n + 1];
7 for (int i = 0; i < n; i++)
8 prefixSum[i + 1] = prefixSum[i] + stones[i];
9 int[,] dp = new int[n, n];
10
11 for (int length = 2; length <= n; length++) {
12 for (int i = 0; i <= n - length; i++) {
13 int j = i + length - 1;
14 int scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
15 int scoreRemoveRight = prefixSum[j] - prefixSum[i];
16 dp[i, j] = Math.Max(scoreRemoveLeft - dp[i+1, j], scoreRemoveRight - dp[i, j-1]);
17 }
18 }
19 return dp[0, n - 1];
20 }
21}
22The C# solution takes advantage of two-dimensional arrays to represent the DP table. Using prefix sums, we efficiently determine the maximum score difference at each decision point, optimizing for the current player's moves.
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)
1using System.Collections.Generic;
public class Solution {
private int dfs(int[] stones, int left, int right, int sum, int[,] memo) {
if (left == right) return 0;
if (memo[left, right] != -1) return memo[left, right];
int removeLeft = sum - stones[left] - dfs(stones, left + 1, right, sum - stones[left], memo);
int removeRight = sum - stones[right] - dfs(stones, left, right - 1, sum - stones[right], memo);
memo[left, right] = Math.Max(removeLeft, removeRight);
return memo[left, right];
}
public int StoneGameVII(int[] stones) {
int sum = 0;
foreach (var stone in stones) sum += stone;
int[,] memo = new int[stones.Length, stones.Length];
for (int i = 0; i < stones.Length; i++)
for (int j = 0; j < stones.Length; j++)
memo[i, j] = -1;
return dfs(stones, 0, stones.Length - 1, sum, memo);
}
}
The C# solution follows a recursive design pattern interwoven with memoization. This provides a mechanism to systematically determine optimal plays by recursively computing without overlaps thanks to the memoization, thus returning optimal score disparities effortlessly.