311. Stone Game

Track the best score DIFFERENCE (current player minus opponent) achievable on each sub-row piles[i..j]. Taking an end scores that pile and hands the rest to the opponent, whose advantage counts against you. Fill sub-rows from short to long; Alice wins iff dp[0][n-1] > 0.

Reframe as a score difference

Instead of tracking two separate scores, track a single number: dp[i][j] = the best score difference (the player to move, minus the other player) that the current player can guarantee when only the sub-row piles[i..j] remains.

Why a difference? Because whatever the opponent scores next comes straight out of your lead. If, after your move, the opponent can guarantee a difference of d in their favor on the leftover row, that is -d from your point of view.

The recurrence

On row piles[i..j] the current player has two choices:

• Take the left pile piles[i]: you gain piles[i], then the opponent plays optimally on piles[i+1..j], guaranteeing dp[i+1][j] for themselves — which is -dp[i+1][j] for you. Net: piles[i] - dp[i+1][j].
• Take the right pile piles[j]: by the same logic, net piles[j] - dp[i][j-1].

Take the better option:

dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

Base case: a single pile, dp[i][i] = piles[i] — you take it, opponent gets nothing.

Fill the table by increasing sub-row length (length 1 first, then 2, ... up to n) so both smaller sub-rows are ready when you need them. The answer is dp[0][n-1] > 0: Alice wins exactly when she can force a positive lead over the whole row.

Worked example

piles = [5, 3, 4, 5]

Length-1 (base): dp[0][0]=5, dp[1][1]=3, dp[2][2]=4, dp[3][3]=5.

Length-2:

• dp[0][1] = max(5 - dp[1][1], 3 - dp[0][0]) = max(5-3, 3-5) = 2.
• dp[1][2] = max(3 - dp[2][2], 4 - dp[1][1]) = max(3-4, 4-3) = 1.
• dp[2][3] = max(4 - dp[3][3], 5 - dp[2][2]) = max(4-5, 5-4) = 1.

Length-3:

• dp[0][2] = max(5 - dp[1][2], 4 - dp[0][1]) = max(5-1, 4-2) = 4.
• dp[1][3] = max(3 - dp[2][3], 5 - dp[1][2]) = max(3-1, 5-1) = 4.

Length-4:

• dp[0][3] = max(5 - dp[1][3], 5 - dp[0][2]) = max(5-4, 5-4) = 1.

dp[0][3] = 1 > 0, so Alice wins → return true.

Complexity

• Time: O(n^2) — one pass over every (i, j) sub-row.
• Space: O(n^2) for the table (compressible to O(n)).

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        // dp[i][j] = best score difference (current player - opponent)
        // achievable on the sub-row piles[i..j].
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i + length - 1 < n; i++) {
                int j = i + length - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0;
    }
}