877. Stone Game - Explanation

Description

Alice and Bob are playing 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 the 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.

Example 1:

Input: piles = [1,2,3,1]

Output: true

Explanation: Alice takes first pile, then Bob takes the last pile, then Alice takes the pile from the end and Bob takes the last remaining pile. Alice's score is 1 + 3 = 4. Bob's score is 1 + 2 = 3.

Example 2:

Input: piles = [2,1]

Output: true

Constraints:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles[i]) is odd.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming (Interval DP) - Computing optimal results over ranges [l, r] with subproblems based on shrinking intervals
Game Theory / Two-Player Games - Understanding how to model turn-based games where both players play optimally
Recursion with Memoization - Converting recursive solutions to efficient DP by caching overlapping subproblems
Mathematical Reasoning - Recognizing that structural properties (even pile count, odd total) can lead to direct solutions

1. Recursion

Intuition

This is a two-player game where Alice and Bob take turns picking from either end of the piles array. Both play optimally, meaning each player maximizes their own score. We can simulate this using recursion where we track the current range [l, r] and determine whose turn it is based on the range length. Alice wants to maximize her score, while Bob's moves affect what Alice can collect later.

Algorithm

Define a recursive function dfs(l, r) that returns Alice's maximum score for the subarray [l, r].
If l > r, return 0 (no piles left).
Determine if it is Alice's turn: it is Alice's turn when the number of remaining piles (r - l + 1) is even.
If it is Alice's turn, she can take from either end and we add her choice to the score. Recurse and take the maximum of taking left or right.
If it is Bob's turn, he takes optimally but we only track Alice's score (add 0 for his pick).
Compare Alice's final score against Bob's (total minus Alice's score) to determine the winner.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        def dfs(l, r):
            if l > r:
                return 0
            even = (r - l) % 2 == 0
            left = piles[l] if even else 0
            right = piles[r] if even else 0
            return max(dfs(l + 1, r) + left, dfs(l, r - 1) + right)

        total = sum(piles)
        alice_score = dfs(0, len(piles) - 1)
        return alice_score > total - alice_score

public class Solution {
    public boolean stoneGame(int[] piles) {
        int total = 0;
        for (int pile : piles) {
            total += pile;
        }

        int aliceScore = dfs(0, piles.length - 1, piles);
        return aliceScore > total - aliceScore;
    }

    private int dfs(int l, int r, int[] piles) {
        if (l > r) {
            return 0;
        }
        boolean even = (r - l) % 2 == 0;
        int left = even ? piles[l] : 0;
        int right = even ? piles[r] : 0;
        return Math.max(dfs(l + 1, r, piles) + left, dfs(l, r - 1, piles) + right);
    }
}

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int total = accumulate(piles.begin(), piles.end(), 0);
        int aliceScore = dfs(0, piles.size() - 1, piles);
        return aliceScore > total - aliceScore;
    }

private:
    int dfs(int l, int r, const vector<int>& piles) {
        if (l > r) {
            return 0;
        }
        bool even = (r - l) % 2 == 0;
        int left = even ? piles[l] : 0;
        int right = even ? piles[r] : 0;
        return max(dfs(l + 1, r, piles) + left, dfs(l, r - 1, piles) + right);
    }
};

class Solution {
    /**
     * @param {number[]} piles
     * @return {boolean}
     */
    stoneGame(piles) {
        const total = piles.reduce((a, b) => a + b, 0);

        const dfs = (l, r) => {
            if (l > r) {
                return 0;
            }
            const even = (r - l) % 2 === 0;
            const left = even ? piles[l] : 0;
            const right = even ? piles[r] : 0;
            return Math.max(dfs(l + 1, r) + left, dfs(l, r - 1) + right);
        };

        const aliceScore = dfs(0, piles.length - 1);
        return aliceScore > total - aliceScore;
    }
}

public class Solution {
    public bool StoneGame(int[] piles) {
        int total = 0;
        foreach (int pile in piles) {
            total += pile;
        }

        int aliceScore = Dfs(0, piles.Length - 1, piles);
        return aliceScore > total - aliceScore;
    }

    private int Dfs(int l, int r, int[] piles) {
        if (l > r) {
            return 0;
        }
        bool even = (r - l) % 2 == 0;
        int left = even ? piles[l] : 0;
        int right = even ? piles[r] : 0;
        return Math.Max(Dfs(l + 1, r, piles) + left, Dfs(l, r - 1, piles) + right);
    }
}

func stoneGame(piles []int) bool {
    total := 0
    for _, pile := range piles {
        total += pile
    }

    var dfs func(l, r int) int
    dfs = func(l, r int) int {
        if l > r {
            return 0
        }
        even := (r-l)%2 == 0
        left, right := 0, 0
        if even {
            left = piles[l]
            right = piles[r]
        }
        return max(dfs(l+1, r)+left, dfs(l, r-1)+right)
    }

    aliceScore := dfs(0, len(piles)-1)
    return aliceScore > total-aliceScore
}

class Solution {
    fun stoneGame(piles: IntArray): Boolean {
        val total = piles.sum()

        fun dfs(l: Int, r: Int): Int {
            if (l > r) return 0
            val even = (r - l) % 2 == 0
            val left = if (even) piles[l] else 0
            val right = if (even) piles[r] else 0
            return maxOf(dfs(l + 1, r) + left, dfs(l, r - 1) + right)
        }

        val aliceScore = dfs(0, piles.size - 1)
        return aliceScore > total - aliceScore
    }
}

class Solution {
    func stoneGame(_ piles: [Int]) -> Bool {
        let total = piles.reduce(0, +)

        func dfs(_ l: Int, _ r: Int) -> Int {
            if l > r { return 0 }
            let even = (r - l) % 2 == 0
            let left = even ? piles[l] : 0
            let right = even ? piles[r] : 0
            return max(dfs(l + 1, r) + left, dfs(l, r - 1) + right)
        }

        let aliceScore = dfs(0, piles.count - 1)
        return aliceScore > total - aliceScore
    }
}

impl Solution {
    pub fn stone_game(piles: Vec<i32>) -> bool {
        let total: i32 = piles.iter().sum();

        fn dfs(l: usize, r: usize, piles: &[i32]) -> i32 {
            if l > r {
                return 0;
            }
            let even = (r - l) % 2 == 0;
            let left = if even { piles[l] } else { 0 };
            let right = if even { piles[r] } else { 0 };
            (dfs(l + 1, r, piles) + left).max(dfs(if l > 0 || r > 0 { l } else { 0 }, r.wrapping_sub(1), piles) + right)
        }

        // Use a safe version to avoid underflow on r
        fn dfs_safe(l: i32, r: i32, piles: &[i32]) -> i32 {
            if l > r {
                return 0;
            }
            let even = (r - l) % 2 == 0;
            let left = if even { piles[l as usize] } else { 0 };
            let right = if even { piles[r as usize] } else { 0 };
            (dfs_safe(l + 1, r, piles) + left).max(dfs_safe(l, r - 1, piles) + right)
        }

        let n = piles.len() as i32;
        let alice_score = dfs_safe(0, n - 1, &piles);
        alice_score > total - alice_score
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems since the same (l, r) range can be reached through different sequences of moves. By memoizing results for each (l, r) pair, we avoid recomputing the same states and achieve polynomial time complexity.

Algorithm

Create a 2D memoization table dp initialized to -1 (or use a hash map).
In the recursive function, first check if dp[l][r] has been computed. If so, return the cached value.
Compute the result as in the plain recursion approach.
Store the result in dp[l][r] before returning.
The final answer is whether dp[0][n-1] (Alice's score) is greater than total - dp[0][n-1] (Bob's score).

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = {}

        def dfs(l, r):
            if l > r:
                return 0
            if (l, r) in dp:
                return dp[(l, r)]
            even = (r - l) % 2 == 0
            left = piles[l] if even else 0
            right = piles[r] if even else 0
            dp[(l, r)] = max(dfs(l + 1, r) + left, dfs(l, r - 1) + right)
            return dp[(l, r)]

        total = sum(piles)
        alice_score = dfs(0, len(piles) - 1)
        return alice_score > total - alice_score

public class Solution {
    private int[][] dp;

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }

        int total = 0;
        for (int pile : piles) {
            total += pile;
        }

        int aliceScore = dfs(0, n - 1, piles);
        return aliceScore > total - aliceScore;
    }

    private int dfs(int l, int r, int[] piles) {
        if (l > r) {
            return 0;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        boolean even = (r - l) % 2 == 0;
        int left = even ? piles[l] : 0;
        int right = even ? piles[r] : 0;
        dp[l][r] = Math.max(dfs(l + 1, r, piles) + left, dfs(l, r - 1, piles) + right);
        return dp[l][r];
    }
}

class Solution {
private:
    vector<vector<int>> dp;

public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        dp = vector<vector<int>>(n, vector<int>(n, -1));
        int total = accumulate(piles.begin(), piles.end(), 0);
        int aliceScore = dfs(0, n - 1, piles);
        return aliceScore > total - aliceScore;
    }

private:
    int dfs(int l, int r, const vector<int>& piles) {
        if (l > r) {
            return 0;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        bool even = (r - l) % 2 == 0;
        int left = even ? piles[l] : 0;
        int right = even ? piles[r] : 0;
        dp[l][r] = max(dfs(l + 1, r, piles) + left, dfs(l, r - 1, piles) + right);
        return dp[l][r];
    }
};

class Solution {
    /**
     * @param {number[]} piles
     * @return {boolean}
     */
    stoneGame(piles) {
        const n = piles.length;
        const dp = Array.from({ length: n }, () => Array(n).fill(-1));

        const dfs = (l, r) => {
            if (l > r) {
                return 0;
            }
            if (dp[l][r] !== -1) {
                return dp[l][r];
            }
            const even = (r - l) % 2 === 0;
            const left = even ? piles[l] : 0;
            const right = even ? piles[r] : 0;
            dp[l][r] = Math.max(dfs(l + 1, r) + left, dfs(l, r - 1) + right);
            return dp[l][r];
        };

        const total = piles.reduce((a, b) => a + b, 0);
        const aliceScore = dfs(0, n - 1);
        return aliceScore > total - aliceScore;
    }
}

public class Solution {
    private int[,] dp;

    public bool StoneGame(int[] piles) {
        int n = piles.Length;
        dp = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = -1;
            }
        }

        int total = 0;
        foreach (int pile in piles) {
            total += pile;
        }

        int aliceScore = Dfs(0, n - 1, piles);
        return aliceScore > total - aliceScore;
    }

    private int Dfs(int l, int r, int[] piles) {
        if (l > r) {
            return 0;
        }
        if (dp[l, r] != -1) {
            return dp[l, r];
        }
        bool even = (r - l) % 2 == 0;
        int left = even ? piles[l] : 0;
        int right = even ? piles[r] : 0;
        dp[l, r] = Math.Max(Dfs(l + 1, r, piles) + left, Dfs(l, r - 1, piles) + right);
        return dp[l, r];
    }
}

class Solution {
    fun stoneGame(piles: IntArray): Boolean {
        val n = piles.size
        val dp = Array(n) { IntArray(n) { -1 } }
        val total = piles.sum()

        fun dfs(l: Int, r: Int): Int {
            if (l > r) return 0
            if (dp[l][r] != -1) return dp[l][r]
            val even = (r - l) % 2 == 0
            val left = if (even) piles[l] else 0
            val right = if (even) piles[r] else 0
            dp[l][r] = maxOf(dfs(l + 1, r) + left, dfs(l, r - 1) + right)
            return dp[l][r]
        }

        val aliceScore = dfs(0, n - 1)
        return aliceScore > total - aliceScore
    }
}

class Solution {
    func stoneGame(_ piles: [Int]) -> Bool {
        let n = piles.count
        var dp = [[Int]](repeating: [Int](repeating: -1, count: n), count: n)
        let total = piles.reduce(0, +)

        func dfs(_ l: Int, _ r: Int) -> Int {
            if l > r { return 0 }
            if dp[l][r] != -1 { return dp[l][r] }
            let even = (r - l) % 2 == 0
            let left = even ? piles[l] : 0
            let right = even ? piles[r] : 0
            dp[l][r] = max(dfs(l + 1, r) + left, dfs(l, r - 1) + right)
            return dp[l][r]
        }

        let aliceScore = dfs(0, n - 1)
        return aliceScore > total - aliceScore
    }
}

impl Solution {
    pub fn stone_game(piles: Vec<i32>) -> bool {
        let n = piles.len();
        let mut dp = vec![vec![-1i32; n]; n];
        let total: i32 = piles.iter().sum();

        fn dfs(l: i32, r: i32, piles: &[i32], dp: &mut Vec<Vec<i32>>) -> i32 {
            if l > r {
                return 0;
            }
            let lu = l as usize;
            let ru = r as usize;
            if dp[lu][ru] != -1 {
                return dp[lu][ru];
            }
            let even = (r - l) % 2 == 0;
            let left = if even { piles[lu] } else { 0 };
            let right = if even { piles[ru] } else { 0 };
            dp[lu][ru] = (dfs(l + 1, r, piles, dp) + left)
                .max(dfs(l, r - 1, piles, dp) + right);
            dp[lu][ru]
        }

        let alice_score = dfs(0, n as i32 - 1, &piles, &mut dp);
        alice_score > total - alice_score
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion with memoization, we can fill the DP table iteratively. We process subproblems in order of increasing range length. For each range [l, r], we compute Alice's optimal score based on already-solved smaller ranges [l+1, r] and [l, r-1].

Algorithm

Create a 2D DP table of size n x n.
Iterate l from n-1 down to 0 (to ensure smaller ranges are solved first).
For each l, iterate r from l to n-1.
Determine whose turn it is based on (r - l) % 2.
For base case l == r, Alice takes the pile if it is her turn, otherwise 0.
For larger ranges, take the maximum of choosing left or right (adding the pile value only on Alice's turn).
Return whether dp[0][n-1] > total - dp[0][n-1].

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

        for l in range(n - 1, -1, -1):
            for r in range(l, n):
                even = (r - l) % 2 == 0
                left = piles[l] if even else 0
                right = piles[r] if even else 0
                if l == r:
                    dp[l][r] = left
                else:
                    dp[l][r] = max(dp[l + 1][r] + left, dp[l][r - 1] + right)

        total = sum(piles)
        alice_score = dp[0][n - 1]
        return alice_score > total - alice_score

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

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                boolean even = (r - l) % 2 == 0;
                int left = even ? piles[l] : 0;
                int right = even ? piles[r] : 0;
                if (l == r) {
                    dp[l][r] = left;
                } else {
                    dp[l][r] = Math.max(dp[l + 1][r] + left, dp[l][r - 1] + right);
                }
            }
        }

        int total = 0;
        for (int pile : piles) {
            total += pile;
        }

        int aliceScore = dp[0][n - 1];
        return aliceScore > total - aliceScore;
    }
}

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

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                bool even = (r - l) % 2 == 0;
                int left = even ? piles[l] : 0;
                int right = even ? piles[r] : 0;
                if (l == r) {
                    dp[l][r] = left;
                } else {
                    dp[l][r] = max(dp[l + 1][r] + left, dp[l][r - 1] + right);
                }
            }
        }

        int total = accumulate(piles.begin(), piles.end(), 0);
        int aliceScore = dp[0][n - 1];
        return aliceScore > total - aliceScore;
    }
};

class Solution {
    /**
     * @param {number[]} piles
     * @return {boolean}
     */
    stoneGame(piles) {
        const n = piles.length;
        const dp = Array.from({ length: n }, () => Array(n).fill(0));

        for (let l = n - 1; l >= 0; l--) {
            for (let r = l; r < n; r++) {
                const even = (r - l) % 2 === 0;
                const left = even ? piles[l] : 0;
                const right = even ? piles[r] : 0;
                if (l === r) {
                    dp[l][r] = left;
                } else {
                    dp[l][r] = Math.max(
                        dp[l + 1][r] + left,
                        dp[l][r - 1] + right,
                    );
                }
            }
        }

        const total = piles.reduce((a, b) => a + b, 0);
        const aliceScore = dp[0][n - 1];
        return aliceScore > total - aliceScore;
    }
}

public class Solution {
    public bool StoneGame(int[] piles) {
        int n = piles.Length;
        int[,] dp = new int[n, n];

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                bool even = (r - l) % 2 == 0;
                int left = even ? piles[l] : 0;
                int right = even ? piles[r] : 0;
                if (l == r) {
                    dp[l, r] = left;
                } else {
                    dp[l, r] = Math.Max(dp[l + 1, r] + left, dp[l, r - 1] + right);
                }
            }
        }

        int total = 0;
        foreach (int pile in piles) {
            total += pile;
        }

        int aliceScore = dp[0, n - 1];
        return aliceScore > total - aliceScore;
    }
}

class Solution {
    fun stoneGame(piles: IntArray): Boolean {
        val n = piles.size
        val dp = Array(n) { IntArray(n) }

        for (l in n - 1 downTo 0) {
            for (r in l until n) {
                val even = (r - l) % 2 == 0
                val left = if (even) piles[l] else 0
                val right = if (even) piles[r] else 0
                dp[l][r] = if (l == r) {
                    left
                } else {
                    maxOf(dp[l + 1][r] + left, dp[l][r - 1] + right)
                }
            }
        }

        val total = piles.sum()
        val aliceScore = dp[0][n - 1]
        return aliceScore > total - aliceScore
    }
}

class Solution {
    func stoneGame(_ piles: [Int]) -> Bool {
        let n = piles.count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)

        for l in stride(from: n - 1, through: 0, by: -1) {
            for r in l..<n {
                let even = (r - l) % 2 == 0
                let left = even ? piles[l] : 0
                let right = even ? piles[r] : 0
                if l == r {
                    dp[l][r] = left
                } else {
                    dp[l][r] = max(dp[l + 1][r] + left, dp[l][r - 1] + right)
                }
            }
        }

        let total = piles.reduce(0, +)
        let aliceScore = dp[0][n - 1]
        return aliceScore > total - aliceScore
    }
}

impl Solution {
    pub fn stone_game(piles: Vec<i32>) -> bool {
        let n = piles.len();
        let mut dp = vec![vec![0i32; n]; n];

        for l in (0..n).rev() {
            for r in l..n {
                let even = (r - l) % 2 == 0;
                let left = if even { piles[l] } else { 0 };
                let right = if even { piles[r] } else { 0 };
                if l == r {
                    dp[l][r] = left;
                } else {
                    dp[l][r] = (dp[l + 1][r] + left).max(dp[l][r - 1] + right);
                }
            }
        }

        let total: i32 = piles.iter().sum();
        let alice_score = dp[0][n - 1];
        alice_score > total - alice_score
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

Intuition

Looking at the DP transitions, dp[l][r] only depends on dp[l+1][r] and dp[l][r-1]. When iterating by increasing l from right to left and r from left to right, we only need values from the current row being built. This allows us to compress the 2D table into a 1D array.

Algorithm

Create a 1D DP array of size n.
Iterate l from n-1 down to 0.
For each l, iterate r from l to n-1.
dp[r] represents the previous value from dp[l+1][r], and dp[r-1] represents dp[l][r-1].
Update dp[r] with the maximum score for the current range.
Return whether dp[n-1] > total - dp[n-1].

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [0] * n

        for l in reversed(range(n)):
            for r in range(l, n):
                even = ((r - l) % 2 == 0)
                left = piles[l] if even else 0
                right = piles[r] if even else 0

                if l == r:
                    dp[r] = left
                else:
                    dp[r] = max(dp[r] + left, dp[r - 1] + right)

        total = sum(piles)
        alice_score = dp[n - 1]
        return alice_score > (total - alice_score)

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

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                boolean even = (r - l) % 2 == 0;
                int left = even ? piles[l] : 0;
                int right = even ? piles[r] : 0;

                if (l == r) {
                    dp[r] = left;
                } else {
                    dp[r] = Math.max(dp[r] + left, dp[r - 1] + right);
                }
            }
        }

        int total = 0;
        for (int pile : piles) {
            total += pile;
        }

        int aliceScore = dp[n - 1];
        return aliceScore > (total - aliceScore);
    }
}

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

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                bool even = (r - l) % 2 == 0;
                int left = even ? piles[l] : 0;
                int right = even ? piles[r] : 0;

                if (l == r) {
                    dp[r] = left;
                } else {
                    dp[r] = max(dp[r] + left, dp[r - 1] + right);
                }
            }
        }

        int total = accumulate(piles.begin(), piles.end(), 0);
        int aliceScore = dp[n - 1];
        return aliceScore > (total - aliceScore);
    }
};

class Solution {
    /**
     * @param {number[]} piles
     * @return {boolean}
     */
    stoneGame(piles) {
        const n = piles.length;
        const dp = new Array(n).fill(0);

        for (let l = n - 1; l >= 0; l--) {
            for (let r = l; r < n; r++) {
                const even = (r - l) % 2 === 0;
                const left = even ? piles[l] : 0;
                const right = even ? piles[r] : 0;

                if (l === r) {
                    dp[r] = left;
                } else {
                    dp[r] = Math.max(dp[r] + left, dp[r - 1] + right);
                }
            }
        }

        const total = piles.reduce((a, b) => a + b, 0);
        const aliceScore = dp[n - 1];
        return aliceScore > total - aliceScore;
    }
}

public class Solution {
    public bool StoneGame(int[] piles) {
        int n = piles.Length;
        int[] dp = new int[n];

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l; r < n; r++) {
                bool even = (r - l) % 2 == 0;
                int left = even ? piles[l] : 0;
                int right = even ? piles[r] : 0;

                if (l == r) {
                    dp[r] = left;
                } else {
                    dp[r] = Math.Max(dp[r] + left, dp[r - 1] + right);
                }
            }
        }

        int total = 0;
        foreach (int pile in piles) {
            total += pile;
        }

        int aliceScore = dp[n - 1];
        return aliceScore > (total - aliceScore);
    }
}

func stoneGame(piles []int) bool {
    n := len(piles)
    dp := make([]int, n)

    for l := n - 1; l >= 0; l-- {
        for r := l; r < n; r++ {
            even := (r-l)%2 == 0
            left, right := 0, 0
            if even {
                left = piles[l]
                right = piles[r]
            }
            if l == r {
                dp[r] = left
            } else {
                dp[r] = max(dp[r]+left, dp[r-1]+right)
            }
        }
    }

    total := 0
    for _, pile := range piles {
        total += pile
    }

    aliceScore := dp[n-1]
    return aliceScore > total-aliceScore
}

class Solution {
    fun stoneGame(piles: IntArray): Boolean {
        val n = piles.size
        val dp = IntArray(n)

        for (l in n - 1 downTo 0) {
            for (r in l until n) {
                val even = (r - l) % 2 == 0
                val left = if (even) piles[l] else 0
                val right = if (even) piles[r] else 0
                dp[r] = if (l == r) {
                    left
                } else {
                    maxOf(dp[r] + left, dp[r - 1] + right)
                }
            }
        }

        val total = piles.sum()
        val aliceScore = dp[n - 1]
        return aliceScore > total - aliceScore
    }
}

class Solution {
    func stoneGame(_ piles: [Int]) -> Bool {
        let n = piles.count
        var dp = [Int](repeating: 0, count: n)

        for l in stride(from: n - 1, through: 0, by: -1) {
            for r in l..<n {
                let even = (r - l) % 2 == 0
                let left = even ? piles[l] : 0
                let right = even ? piles[r] : 0
                if l == r {
                    dp[r] = left
                } else {
                    dp[r] = max(dp[r] + left, dp[r - 1] + right)
                }
            }
        }

        let total = piles.reduce(0, +)
        let aliceScore = dp[n - 1]
        return aliceScore > total - aliceScore
    }
}

impl Solution {
    pub fn stone_game(piles: Vec<i32>) -> bool {
        let n = piles.len();
        let mut dp = vec![0i32; n];

        for l in (0..n).rev() {
            for r in l..n {
                let even = (r - l) % 2 == 0;
                let left = if even { piles[l] } else { 0 };
                let right = if even { piles[r] } else { 0 };
                if l == r {
                    dp[r] = left;
                } else {
                    dp[r] = (dp[r] + left).max(dp[r - 1] + right);
                }
            }
        }

        let total: i32 = piles.iter().sum();
        let alice_score = dp[n - 1];
        alice_score > total - alice_score
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

5. Return TRUE

Intuition

Here is the key insight: with an even number of piles and an odd total sum, Alice can always win. She can always choose to take all even-indexed piles or all odd-indexed piles. Since the total is odd, one of these sets must have a larger sum. Alice, moving first, can force the game to give her whichever set she prefers, guaranteeing a win.

Algorithm

Simply return true.

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Overcomplicating the Solution

The mathematical insight that Alice always wins (due to even pile count and odd total) means you can simply return true. However, many solvers implement full DP without recognizing this property. While the DP approach is valid and educational, understanding why Alice always wins demonstrates deeper problem analysis.

Confusing Whose Turn It Is

In the DP approach, determining whose turn it is based on the range [l, r] can be tricky. Alice moves when the number of remaining piles is even (since the game starts with an even number and she goes first). Using (r - l + 1) % 2 == 0 or equivalently (r - l) % 2 == 1 indicates Alice's turn, but off-by-one errors here are common.

Wrong Comparison for Final Result

The question asks whether Alice wins (strictly greater score), not whether she ties or wins. Comparing alice_score >= total - alice_score instead of alice_score > total - alice_score gives incorrect results. Since the total is odd and all values are positive integers, a tie is impossible in this specific problem, but the comparison should still be strictly greater.