In the Stone Game III problem, you are given an array stoneValue where each element represents the value of a stone in a row. Two players, Alice and Bob, take turns playing. On each turn, a player can take the first 1, 2, or 3 stones from the row (i.e., from the start of the remaining stones). The player who takes the stones adds their values to their own score, and the stones are removed from the row.
Both players play optimally, meaning they try to maximize their own score. The game continues until all stones are taken. At the end, the player with the higher score wins. If both scores are equal, the result is a tie.
"Alice" if Alice wins, "Bob" if Bob wins, or "Tie" if their scores are equal.1 <= stoneValue.length <= 5 * 10^4, -1000 <= stoneValue[i] <= 1000At first glance, this problem seems to require simulating every possible sequence of moves for both players, as each can choose to take 1, 2, or 3 stones on their turn. However, this brute-force approach quickly becomes infeasible due to the exponential number of possible move sequences.
To optimize, we recognize that the game is about maximizing the difference between the current player's score and the opponent's, assuming both play optimally. This is a classic case for dynamic programming: we can define the problem recursively in terms of the best possible outcome from any given starting point, and use memoization or tabulation to avoid recalculating states.
The key insight is to work backwards: for each position in the array, we can calculate the best net score difference the current player can achieve, considering all possible moves (taking 1, 2, or 3 stones).
To solve the problem efficiently, we use dynamic programming. Here’s a step-by-step breakdown:
dp[i] represent the maximum net score difference the current player can achieve starting from index i in stoneValue. A positive value means the current player is ahead; negative means behind.
i is at or beyond the end of the array, there are no stones left, so dp[i] = 0.
i, try taking 1, 2, or 3 stones (if available). For each choice:
i + x (where x is the number of stones taken).current_sum - dp[i + x] (because the opponent gets to play optimally from the new position).dp, look at dp[0]:
dp[0] > 0, Alice wins.dp[0] < 0, Bob wins.dp[0] == 0, it's a tie.
Let's walk through an example with stoneValue = [1,2,3,7]:
i = 3 (stoneValue[3] = 7), Alice can only take one stone:
dp[3] = 7.i = 2 (stoneValue[2] = 3):
dp[3] = 7, so net = 3 - 7 = -4.10 - 0 = 10.dp[2] = max(-4, 10) = 10.i = 1 (stoneValue[1] = 2):
dp[2] = 10, net = 2 - 10 = -8.dp[3] = 7, net = 5 - 7 = -2.12 - 0 = 12.dp[1] = max(-8, -2, 12) = 12.i = 0 (stoneValue[0] = 1):
dp[1] = 12, net = 1 - 12 = -11.dp[2] = 10, net = 3 - 10 = -7.dp[3] = 7, net = 6 - 7 = -1.dp[0] = max(-11, -7, -1) = -1.dp[0] = -1, Alice is behind by 1 point, so Bob wins.
O(n), as we process each index once and for each index, only consider up to 3 options.O(n) for the DP array. (Can be reduced to O(1) with rolling variables, but O(n) is standard and clear.)The Stone Game III problem is a classic example of applying dynamic programming to a two-player, turn-based game with optimal strategies. By modeling the game as a series of state transitions and calculating the maximum net score difference at each step, we efficiently determine the winner. The elegance of the solution lies in reducing an exponential search space to a linear-time dynamic programming approach, making it both efficient and conceptually clear.
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
max_diff = float('-inf')
take = 0
for k in range(1, 4):
if i + k - 1 < n:
take += stoneValue[i + k - 1]
max_diff = max(max_diff, take - dp[i + k])
dp[i] = max_diff
if dp[0] > 0:
return "Alice"
elif dp[0] < 0:
return "Bob"
else:
return "Tie"
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
int maxDiff = INT_MIN, take = 0;
for (int k = 1; k <= 3; ++k) {
if (i + k - 1 < n) {
take += stoneValue[i + k - 1];
maxDiff = max(maxDiff, take - dp[i + k]);
}
}
dp[i] = maxDiff;
}
if (dp[0] > 0) return "Alice";
else if (dp[0] < 0) return "Bob";
else return "Tie";
}
};
class Solution {
public String stoneGameIII(int[] stoneValue) {
int n = stoneValue.length;
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; --i) {
int maxDiff = Integer.MIN_VALUE, take = 0;
for (int k = 1; k <= 3; ++k) {
if (i + k - 1 < n) {
take += stoneValue[i + k - 1];
maxDiff = Math.max(maxDiff, take - dp[i + k]);
}
}
dp[i] = maxDiff;
}
if (dp[0] > 0) return "Alice";
else if (dp[0] < 0) return "Bob";
else return "Tie";
}
}
var stoneGameIII = function(stoneValue) {
const n = stoneValue.length;
const dp = new Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; --i) {
let maxDiff = -Infinity, take = 0;
for (let k = 1; k <= 3; ++k) {
if (i + k - 1 < n) {
take += stoneValue[i + k - 1];
maxDiff = Math.max(maxDiff, take - dp[i + k]);
}
}
dp[i] = maxDiff;
}
if (dp[0] > 0) return "Alice";
else if (dp[0] < 0) return "Bob";
else return "Tie";
};