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.
1#include <stdio.h>
2#include <string.h>
3
4int stoneGameIII(int* stoneValue, int stoneValueSize) {
5 int dp[stoneValueSize + 1];
6 memset(dp, -1, sizeof(dp));
7
8 dp[stoneValueSize] = 0; // Base case
9
10 for (int i = stoneValueSize - 1; i >= 0; --i) {
11 int take = 0;
12 dp[i] = -1001; // A very small number to ensure it gets maximized
13 for (int k = 0; k < 3 && i + k < stoneValueSize; ++k) {
14 take += stoneValue[i + k];
15 dp[i] = fmax(dp[i], take - dp[i + k + 1]);
16 }
17 }
18
19 if (dp[0] > 0) return "Alice";
20 else if (dp[0] < 0) return "Bob";
21 else return "Tie";
22}
23The code initializes a DP array to store maximum scores achievable from each position. It iterates backward through the stone array, calculating for each position the maximum score difference possible by taking 1, 2, or 3 stones and subtracting the opponent's best response.
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.