石子游戏中，爱丽丝和鲍勃轮流进行自己的回合， 爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和
相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都
发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

**输入：** stones = [5,3,1,4,2]
**输出：** 6
**解释：**
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。

示例 2：

**输入：** stones = [7,90,5,1,100,10,10,2]
**输出：** 122

提示：

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

解法

思路和算法

由于每次只能从剩余石子中的任意一端取一个石子，因此剩余的石子一定是数组 stones 中的连续子数组，可以使用开始下标和结束下标表示子数组。剩余石子值之和为一个子数组的元素值之和，对于 i \le j，用 sum}(i, j) 表示数组 stones 的下标范围 [i, j] 的子数组的元素值之和。

为了快速计算数组 stones 的子数组的元素值之和，需要预计算数组 stones 的前缀和数组。用 n 表示数组 stones 的长度。创建长度为 n + 1 的数组 prefixSums，其中 prefixSums}[0] = 0，对于 0 \le i < n 有 prefixSums}[i + 1] = \textit{prefixSums}[i] + \textit{stones}[i]。计算前缀和数组之后，有如下结论。

对于 0 \le i \le n，prefixSums}[i] 为数组 stones 的长度为 i 的前缀的元素值之和。
对于 0 \le i \le j < n，数组 stones 的下标范围 [i, j] 的子数组的元素值之和为 prefixSums}[j + 1] - \textit{prefixSums}[i]。

当前玩家取一个石子之后，剩余的子数组的长度减 1，对方玩家在更短的子数组中取一个石子，因此可以使用动态规划计算游戏结果。

创建 n \times n 的二维数组 dp，其中 dp}[i][j] 为区间 [i, j] 中的当前玩家与对方玩家的得分的最大差值。

当 i = j 时，子数组中只有一个石子，当前玩家只能取 stones}[i]，之后没有剩余石子，当前玩家与对方玩家的得分的差值是 0，因此动态规划的边界情况是：对于 0 \le i < n，dp}[i][i] = 0。

当 i < j 时，当前玩家可以取 stones}[i] 或 stones}[j]，对应的己方与对方的得分的差值分别是 sum}(i + 1, j) - \textit{dp}[i + 1][j] 和 sum}(i, j - 1) - \textit{dp}[i][j - 1]，当前玩家应使己方与对方得分的差值最大化，因此动态规划的状态转移方程是 dp}[i][j] = \max(\textit{sum}(i + 1, j) - \textit{dp}[i + 1][j], \textit{sum}(i, j - 1) - \textit{dp}[i][j - 1])。

代入前缀和数组，动态规划的状态转移方程是 dp}[i][j] = \max(\textit{prefixSums}[j + 1] - \textit{prefixSums}[i + 1] - \textit{dp}[i + 1][j], \textit{prefixSums}[j] - \textit{prefixSums}[i] - \textit{dp}[i][j - 1])。

根据动态规划的状态转移方程，计算 dp}[i][j] 需要使用 dp}[i + 1][j] 和 dp}[i][j - 1] 的值，即区间 [i + 1, j] 和 [i, j - 1] 的状态值需要在区间 [i, j] 的状态值之前计算，因此计算 dp}[i][j] 的顺序可以是以下两种。

从小到大遍历每个区间长度，对于每个区间长度依次计算每个区间的状态值。
从大到小遍历每个区间开始下标 i，对于每个区间开始下标 i 从小到大遍历每个区间结束下标 j，依次计算每个区间 [i, j] 的状态值。

计算得到 dp}[0][n - 1] 即为 Alice 与 Bob 的得分的最大差值。

代码

下面的代码为按照区间长度递增顺序计算的实现。

[sol1_1-Java]class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + stones[i];
        }
        int[][] dp = new int[n][n];
        for (int subLength = 2; subLength <= n; subLength++) {
            for (int i = 0, j = subLength - 1; j < n; i++, j++) {
                dp[i][j] = Math.max(getRangeSum(prefixSums, i + 1, j) - dp[i + 1][j], getRangeSum(prefixSums, i, j - 1) - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }

    public int getRangeSum(int[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

[sol1_1-C#]public class Solution {
    public int StoneGameVII(int[] stones) {
        int n = stones.Length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + stones[i];
        }
        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n];
        }
        for (int subLength = 2; subLength <= n; subLength++) {
            for (int i = 0, j = subLength - 1; j < n; i++, j++) {
                dp[i][j] = Math.Max(GetRangeSum(prefixSums, i + 1, j) - dp[i + 1][j], GetRangeSum(prefixSums, i, j - 1) - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }

    public int GetRangeSum(int[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

下面的代码为按照区间开始下标递减顺序计算的实现。

[sol1_2-Java]class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + stones[i];
        }
        int[][] dp = new int[n][n];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(getRangeSum(prefixSums, i + 1, j) - dp[i + 1][j], getRangeSum(prefixSums, i, j - 1) - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }

    public int getRangeSum(int[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

[sol1_2-C#]public class Solution {
    public int StoneGameVII(int[] stones) {
        int n = stones.Length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + stones[i];
        }
        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n];
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.Max(GetRangeSum(prefixSums, i + 1, j) - dp[i + 1][j], GetRangeSum(prefixSums, i, j - 1) - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }

    public int GetRangeSum(int[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是数组 stones 的长度。计算前缀和数组的时间是 O(n)，动态规划的状态数是 O(n^2)，每个状态的计算时间是 O(1)，因此时间复杂度是 O(n^2)。
空间复杂度：O(n^2)，其中 n 是数组 stones 的长度。需要创建长度为 n + 1 的前缀和数组 prefixSums 与大小为 n \times n 的二维数组 dp。

1690-石子游戏 VII

解法

思路和算法

代码

复杂度分析