Sponsored
Sponsored
This approach involves using dynamic programming to evaluate possible outcomes from the end of the stone array to the beginning. This allows us to make optimal decisions at each step because we know the best scores for the rest of the game. The idea is to calculate the maximum score difference Alice can enforce using a suffix-based strategy.
Time Complexity: O(n), where n is the number of stones. Each stone position is computed once.
Space Complexity: O(n), where n is the number of stones. It uses an array of size n+1 to store computed values.
1var stoneGameIII = function(stoneValue) {
2 const n = stoneValue.length;
3 const dp = new Array(n + 1).fill(Number.MIN_SAFE_INTEGER);
4 dp[n] = 0;
5
6 for (let i = n - 1; i >= 0; i--) {
7 let take = 0;
8 for (let k = 0; k < 3 && (i + k) < n; k++) {
9 take += stoneValue[i + k];
10 dp[i] = Math.max(dp[i], take - dp[i + k + 1]);
11 }
12 }
13
14 return dp[0] > 0 ? "Alice" : dp[0] < 0 ? "Bob" : "Tie";
15};
16The JavaScript solution utilizes an array for dynamic programming computation, examining each position backward. It computes the optimal game outcome using a difference strategy by deciding the number of stones Alice may take (1, 2, or 3).
This approach leverages the recursive computation of outcomes with memoization. We recursively compute the score differences at each step, caching the results to avoid redundant calculations. At each stone index, the player's optimal score is determined by considering 1 to 3 stone choices.
Time Complexity: O(n), due to computation of score differences for unique indices once per index.
Space Complexity: O(n), from the recursive call stack and memoization cache storing outcomes for each state.
1def stoneGameIII(stoneValue):
2 from functools import lru_cache
3
4
The Python solution employs a memoization decorator to cache previously computed results, optimizing recursive calls. This avoids recalculating results for subproblems, ensuring efficiency. Each call makes decisions based on potential stone selections and returns the best achievable score differential for Alice.