题目

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

有 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

思路

动态规划
核心思想：
时间复杂度：O(n^2)
空间复杂度：O(n^2)

解法

class Solution {
    public int stoneGameVII(int[] stones) {
        int len = stones.length;
        //dp数组，dp[i][j]表示从i到j两人最后的最大差值
        int[][] dp = new int[len][len];
        //pre数组，为的是求拿去stones[i]或stones[j]之后元素的和
        //pre[i + 1]表示stones[0] + stones[1] + stones[2] + ... + stones[i] (i的范围:[0, len - 1])
        int[] pre = new int[len + 1];
        for(int i = 0; i < len; i++)
            pre[i + 1] = pre[i] + stones[i];

        //dp数组初始化：len = j - i + 1 = 1
        //dp[i][j]
        //可以注释掉，便于理解暂时不注释掉
        for(int i = 0; i < len; i++) 
            dp[i][i] = 0;
        
        //len >= 2
        for(int k = 2; k <= len; k++) {
            for(int i = 0; i + k - 1 <= len - 1; i++) {
                //根据i和长度计算j
                int j = i + k - 1;
                //第一个人：[0, j] - [0, i] ==> (i, j]
                //第二个人：dp[i + 1][j]
                //第一个人：[0, j - 1] - [0, i - 1] ==> [i, j)
                //第二个人：dp[i][j - 1]
                //计算差值
                dp[i][j] = Math.max(pre[j + 1] - pre[i + 1] - dp[i + 1][j], pre[j] - pre[i] - dp[i][j - 1]);
            }
        }
        return dp[0][len - 1];
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现