1563. Stone Game V

Array Math Dynamic Programming Game Theory

Problem Overview

On each turn the row is split into two non-empty contiguous parts; the heavier sum is discarded (either if equal) and the current player scores the kept sum, then the opponent plays on what remains.

Intuition

On each turn the row is split into two non-empty contiguous parts; the heavier sum is discarded (either if equal) and the current player scores the kept sum, then the opponent plays on what remains. Alice's optimal score on an interval is interval DP: try every split, take the legal keep-side, and memoize with prefix sums for O(1) range sums.

Algorithm

1Build prefix sums. Memoize dp[i][j] = best score for the player to move on stoneValue[i..j].
2Base: i == j returns 0 (cannot split).
3For each split p in [i, j): leftSum = sum(i..p), rightSum = sum(p+1..j).
4If leftSum < rightSum, keep left: candidate = leftSum + dp[i][p].
5If leftSum > rightSum, keep right: candidate = rightSum + dp[p+1][j].
6If equal, take the max of both options. dp[i][j] is the max over splits.

Example Walkthrough

Input: stoneValue = [6, 2, 3, 4, 5, 5]

1.Alice tries every first split; equal-sum splits let her pick the side that yields more later points.
2.With optimal replies from Bob, her total score reaches 18.

Output: 18

Common Pitfalls

•Discard the larger sum side - the player does not freely choose which side to keep unless the sums tie.
•Only the kept sum is scored that turn; discarded stones never score for anyone.
•Use prefix sums - naive range summing inside O(n^2) splits is too slow.
•A single remaining stone ends the game with score 0 for that state.

1563.cs

// Approach: Interval DP with memo. On stoneValue[i..j], try every split p.
// Compare left/right prefix sums: discard the heavier side (either if equal),
// add the kept sum to the recursive best on the kept interval. Alice maximizes.
// Complexity: O(n^3) time and O(n^2) space.
public class Solution
{
    public int StoneGameV(int[] stoneValue)
    {
        int n = stoneValue.Length;
        int[][] mem = new int[n][];
        for (int i = 0; i < n; i++)
        {
            mem[i] = new int[n];
            Array.Fill(mem[i], int.MinValue);
        }
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + stoneValue[i];
        return StoneGameV(stoneValue, 0, n - 1, prefix, mem);
    }

    // Returns the maximum score that Alice can obtain from stoneValue[i..j].
    private int StoneGameV(int[] stoneValue, int i, int j, int[] prefix, int[][] mem)
    {
        if (i == j)
            return 0;
        if (mem[i][j] != int.MinValue)
            return mem[i][j];

        for (int p = i; p < j; ++p)
        {
            int leftSum = prefix[p + 1] - prefix[i];
            int throwRight = leftSum + StoneGameV(stoneValue, i, p, prefix, mem);
            int rightSum = prefix[j + 1] - prefix[p + 1];
            int throwLeft = rightSum + StoneGameV(stoneValue, p + 1, j, prefix, mem);
            if (leftSum < rightSum)
                mem[i][j] = Math.Max(mem[i][j], throwRight);
            else if (leftSum > rightSum)
                mem[i][j] = Math.Max(mem[i][j], throwLeft);
            else
                mem[i][j] = Math.Max(Math.Max(mem[i][j], throwLeft), throwRight);
        }

        return mem[i][j];
    }
}

Was this solution helpful?