Stone Game

Alex and Lee 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. Alex starts first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left. The person with more stones wins.

The key insight: since the total number of stones is odd, there’s always a winner.

We use dynamic programming. Let dp[i][j] represent the maximum stones the current player can get over the opponent when considering piles from index i to j.

The state equation:

dp[i][j].first = max(piles[i] + dp[i+1][j].second, 
                     piles[j] + dp[i][j-1].second)
dp[i][j].second = the remaining stones after the optimal choice

Here’s the implementation:

bool stoneGame(vector<int>& piles) {
    int len = piles.size();
    vector<vector<pair<int, int>>> dp(piles.size(), 
        vector<pair<int, int>>(len, make_pair(0,0)));
    
    for(int i = 0; i < len; ++i) {
        dp[i][i].first = piles[i];
    }

    for(int i = len-2; i >= 0; --i) {
        for(int j = i+1; j < len; ++j) {
            if (piles[i] + dp[i+1][j].second > 
                piles[j] + dp[i][j-1].second) {
                dp[i][j].first = piles[i] + dp[i+1][j].second;
                dp[i][j].second = dp[i+1][j].first;
            } else {
                dp[i][j].first = piles[j] + dp[i][j-1].second;
                dp[i][j].second = dp[i][j-1].first;
            }
        }
    }

    return dp[0][len-1].first > dp[0][len-1].second;
}

We can compress the space complexity. Since we only need the previous row, we can reduce it to one dimension:

bool stoneGame(vector<int>& piles) {
    int len = piles.size();
    vector<pair<int, int>> dp(piles.size(), make_pair(0,0));
    
    for(int i = 0; i < len; ++i)
        dp[i].first = piles[i];

    for(int i = len-2; i >= 0; --i) {
        for(int j = i+1; j < len; ++j) {
            int c1 = piles[i] + dp[j].second;
            int c2 = piles[j] + dp[j-1].second;
            
            if (c1 > c2) {
                dp[j].second = dp[j].first;
                dp[j].first = c1;
            } else {
                dp[j].second = dp[j-1].first;
                dp[j].first = c2;
            }
        }
    }

    return dp[len-1].first > dp[len-1].second;
}

This solution runs in O(n²) time and O(n) space. The beauty lies in how we model the game as a difference between what the current player gets versus their opponent.

#DP

Stock Trading Problems: From One Deal to K Deals String Permutation Detection: Two Sliding Window Approaches