Stone Game I

XXX. Stone Game

Dynamic Programming

Math

Game Theory

Problem Statement:

Alex and Lee play a game with piles of stones where Alex always goes first. The goal of the game is to determine whether Alex can always win given optimal play by both players. The game can be solved using mathematical insight or dynamic programming.

Algorithm:

1. Mathematical Insight:
   • The number of piles is always even, so Alex can always choose a strategy to ensure victory by taking either all odd-indexed or even-indexed piles based on their sum.
2. Dynamic Programming:
   • Use a 2D DP array where dp[i][j] represents the value of the game for the subarray piles[i...j].
   • If it is Alex's turn, maximize the score by choosing the left or right pile and adding it to the DP result of the remaining subarray.
   • If it is Lee's turn, minimize the score by choosing the left or right pile and subtracting it from the DP result of the remaining subarray.

Complexity:

Time Complexity: O(n²), where n is the number of piles.
Space Complexity: O(n²) for the DP table.

Java Implementation:

// Mathematical solution
public boolean stoneGame(int[] piles) {
    return true;
}

// Dynamic Programming solution
public boolean stoneGameDp(int[] piles) {
    int N = piles.length;
    int[][] dp = new int[N + 2][N + 2];

    for (int size = 1; size <= N; ++size)
        for (int i = 0; i + size <= N; ++i) {
            int j = i + size - 1;
            int parity = (j + i + N) % 2;  // Determine whose turn it is
            if (parity == 1)
                dp[i + 1][j + 1] = Math.max(
                    piles[i] + dp[i + 2][j + 1],
                    piles[j] + dp[i + 1][j]
                );
            else
                dp[i + 1][j + 1] = Math.min(
                    -piles[i] + dp[i + 2][j + 1],
                    -piles[j] + dp[i + 1][j]
                );
        }

    return dp[1][N] > 0;
}
                

Python Implementation:

def stone_game(piles):
    # Mathematical solution
    return True

def stone_game_dp(piles):
    N = len(piles)
    dp = [[0] * (N + 2) for _ in range(N + 2)]

    for size in range(1, N + 1):
        for i in range(N - size + 1):
            j = i + size - 1
            parity = (j + i + N) % 2
            if parity == 1:
                dp[i + 1][j + 1] = max(
                    piles[i] + dp[i + 2][j + 1],
                    piles[j] + dp[i + 1][j]
                )
            else:
                dp[i + 1][j + 1] = min(
                    -piles[i] + dp[i + 2][j + 1],
                    -piles[j] + dp[i + 1][j]
                )

    return dp[1][N] > 0
                

C++ Implementation:

#include 
using namespace std;

// Mathematical solution
bool stoneGame(vector& piles) {
    return true;
}

// Dynamic Programming solution
bool stoneGameDp(vector& piles) {
    int N = piles.size();
    vector> dp(N + 2, vector(N + 2, 0));

    for (int size = 1; size <= N; ++size) {
        for (int i = 0; i + size <= N; ++i) {
            int j = i + size - 1;
            int parity = (j + i + N) % 2;
            if (parity == 1)
                dp[i + 1][j + 1] = max(
                    piles[i] + dp[i + 2][j + 1],
                    piles[j] + dp[i + 1][j]
                );
            else
                dp[i + 1][j + 1] = min(
                    -piles[i] + dp[i + 2][j + 1],
                    -piles[j] + dp[i + 1][j]
                );
        }
    }

    return dp[1][N] > 0;
}