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.
1def stoneGameIII(stoneValue):
2 n = len(stoneValue)
3 dp = [float('-inf')] * (n + 1)
4 dp[n] = 0
5
6 for i in range(n - 1, -1, -1):
7 take = 0
8 for k in range(3):
9 if i + k < n:
10 take += stoneValue[i + k]
11 dp[i] = max(dp[i], take - dp[i + k + 1])
12
13 if dp[0] > 0:
14 return 'Alice'
15 elif dp[0] < 0:
16 return 'Bob'
17 else:
18 return 'Tie'
19In this Python solution, a list of size n + 1 is used for the DP table, initialized to negative infinity. The function processes the list backward, computing the best possible outcome by evaluating 1 to 3 stone picks.
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.