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)
#include <numeric>
#include <algorithm>
class Solution {
public:
int stoneGameVII(std::vector<int>& stones) {
int n = stones.size();
std::vector<int> prefixSum(n + 1, 0);
for (int i = 0; i < n; ++i) prefixSum[i + 1] = prefixSum[i] + stones[i];
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
for (int length = 2; length <= n; ++length) {
for (int i = 0; i <= n - length; ++i) {
int j = i + length - 1;
int scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
int scoreRemoveRight = prefixSum[j] - prefixSum[i];
dp[i][j] = std::max(scoreRemoveLeft - dp[i + 1][j], scoreRemoveRight - dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
};
The C++ solution utilizes vector containers to manage prefix sums and the DP table. Similarly, as in the C implementation, prefix sums are calculated to manage sum queries over subarrays efficiently. The 2D DP vector is then iteratively filled based on the differences between optimal scores when removing stones from either end.
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)
1class Solution:
2 def stoneGameVII(self, stones: List[int]) -> int:
3 def dfs(left, right, sum_):
4 if left == right:
5 return 0
6 if (left, right) in memo:
7 return memo[(left, right)]
8 removeLeft = sum_ - stones[left] - dfs(left + 1, right, sum_ - stones[left])
9 removeRight = sum_ - stones[right] - dfs(left, right - 1, sum_ - stones[right])
10 memo[(left, right)] = max(removeLeft, removeRight)
11 return memo[(left, right)]
12
13 total = sum(stones)
14 memo = {}
15 return dfs(0, len(stones) - 1, total)
16The Python solution uses recursive depth-first search combined with a dictionary for memoization to optimize state explorations. Each game state leads to further recursion unless already encountered, in which case stored results are used, thereby shortening decision times.