Stone Game

Problem Description

Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones across all piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

Examples

Constraints

• 2 ≤ piles.length ≤ 500
• piles.length is even.
• 1 ≤ piles[i] ≤ 500
• sum(piles[i]) is odd.

Math Shortcut: The First Player Always Wins

Because the number of piles is even, Alice can partition the piles into two groups: those at even indices and those at odd indices.

• Sum of even indices: piles[0] + piles[2] + ...
• Sum of odd indices: piles[1] + piles[3] + ...

Since the total sum of stones is odd, one of these two sums must be strictly greater than the other. Alice can choose to take either the first pile (even index) or the last pile (odd index, since length is even).

• If she wants all even piles, she takes the first pile. Bob is then forced to expose an odd pile.
• If she wants all odd piles, she takes the last pile. Bob is then forced to expose an even pile.

By following this strategy, Alice can guarantee she gets whichever group has the larger sum. Since there are no ties, Alice always wins. Thus, the solution is always to return true.

2D DP Solution (For Interview Rigor)

If an interviewer asks you to solve this without using the math shortcut (e.g. if the rules were slightly different or the number of piles was odd), we can use interval DP.

Let dp[i][j] be the maximum relative score difference the current player can achieve from piles [i..j].

• If the current player takes piles[i], they get piles[i] - dp[i + 1][j].
• If the current player takes piles[j], they get piles[j] - dp[i][j - 1].

Thus, the transition is: dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])

We compute this from shorter intervals to longer intervals. If dp[0][n - 1] > 0, Alice wins.

Solution 1: Mathematical Cheat (O(1))

class Solution {
    public boolean stoneGame(int[] piles) {
        return true; // Alice can always choose to get all odd or all even piles
    }
}

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        return True

class Solution {
public:
    bool stoneGame(std::vector<int>& piles) {
        return true;
    }
};

Solution 2: Interval DP (O(N²))

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }

        return dp[0][n - 1] > 0;
    }
}

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = piles[i]

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])

        return dp[0][n - 1] > 0

#include <vector>
#include <algorithm>

class Solution {
public:
    bool stoneGame(std::vector<int>& piles) {
        int n = piles.size();
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = std::max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }

        return dp[0][n - 1] > 0;
    }
};

← All Problems