1522. Stone Game III
My accepted C++ solution to LeetCode problem 1522, Stone Game III, running in 11ms.
- Difficulty: Hard
- C++
- Runtime 11ms
- Memory 136MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
C++
Accepted on LeetCode — runtime 11ms, memory 136MB, accepted 2025-12-27.
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--) {
dp[i] = INT_MIN;
int sum = 0;
for (int k = 1; k <= 3 && i + k <= n; k++) {
sum += stoneValue[i + k - 1];
dp[i] = max(dp[i], sum - dp[i + k]);
}
}
if (dp[0] > 0) return "Alice";
if (dp[0] < 0) return "Bob";
return "Tie";
}
};