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.
1public class StoneGameIII {
2 public String stoneGameIII(int[] stoneValue) {
3 int n = stoneValue.length;
4 int[] dp = new int[n + 1];
5 dp[n] = 0; // Game over condition
6
7 for (int i = n - 1; i >= 0; i--) {
8 int take = 0;
9 dp[i] = Integer.MIN_VALUE;
10 for (int k = 0; k < 3 && i + k < n; k++) {
11 take += stoneValue[i + k];
12 dp[i] = Math.max(dp[i], take - dp[i + k + 1]);
13 }
14 }
15
16 if (dp[0] > 0) return "Alice";
17 else if (dp[0] < 0) return "Bob";
18 else return "Tie";
19 }
20}
21The Java implementation employs an integer array for dynamic programming. Alice's potential maximum score difference is computed by selecting up to three consecutive stones starting from the end.
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.