石子游戏3

2020-12-13

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

有 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
通过次数953提交次数3,127

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stone-game-vii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

无论是B想要缩短价值差，或者A想要扩大价值差，其本质就是这次取法能得到与对手最大的价值差
所以这次DP也用类似的状态。

又因为每次删掉之后的得分是区间累加和，所以又涉及到区间和，所以需要维护
dp[i][j] : 表示从 i 到 j 的区间和
res[i][j]:表示轮到这一个人选时，石头剩下 i 到 j ，他能获得的最大价值差

接下来来推状态转移方程：

最初始的时候：i == j ，res[i][j] = 0，因为删了之后没得取
当 j - i == 1时，res[i][j] = max(stones[i], stones[j])，因为我要利益最大化，我肯定删掉一个较小的石头，取最大得分，反正下一个人是没分的
当j - i > 1时， res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1]),
        本次选取，我只能从左端删或者从右端删，
从左端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i + 1][j]
从右端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i][j - 1]
所以我考虑本次差值最大，那么本次删掉的时候我能得到的最大差值应该是删掉一个之后得到的区间和，减去对手下次选时与我的差值
所以转移方程为： res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1])
最后返回res[0][n - 1]即为我们所需的答案，表示剩下的石头为0到n - 1，Alice能取得的最大价值差

作者：spacex-1
链接：https://leetcode-cn.com/problems/stone-game-vii/solution/c-qu-jian-dp-si-lu-zheng-li-guo-cheng-by-3h0l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    public static int stoneGameVII(int[] stones) {

//        无论是B想要缩短价值差，或者A想要扩大价值差，其本质就是这次取法能得到与对手最大的价值差
//        所以这次DP也用类似的状态。
//
//        又因为每次删掉之后的得分是区间累加和，所以又涉及到区间和，所以需要维护
//        dp[i][j] : 表示从 i 到 j 的区间和
//        res[i][j]:表示轮到这一个人选时，石头剩下 i 到 j ，他能获得的最大价值差
//
//        接下来来推状态转移方程：
//
//        最初始的时候：i == j ，res[i][j] = 0，因为删了之后没得取
//        当 j - i == 1时，res[i][j] = max(stones[i], stones[j])，因为我要利益最大化，我肯定删掉一个较小的石头，取最大得分，反正下一个人是没分的
//        当j - i > 1时， res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1]),
//                本次选取，我只能从左端删或者从右端删，
//        从左端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i + 1][j]
//        从右端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i][j - 1]
//        所以我考虑本次差值最大，那么本次删掉的时候我能得到的最大差值应该是删掉一个之后得到的区间和，减去对手下次选时与我的差值
//        所以转移方程为： res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1])
//        最后返回res[0][n - 1]即为我们所需的答案，表示剩下的石头为0到n - 1，Alice能取得的最大价值差
//
//        作者：spacex-1
//        链接：https://leetcode-cn.com/problems/stone-game-vii/solution/c-qu-jian-dp-si-lu-zheng-li-guo-cheng-by-3h0l/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        int n = stones.length;

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) dp[i][j] = stones[i]; //记录区间和
                else dp[i][j] = stones[j] + dp[i][j - 1];
            }
        }

        int res[][] = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {//左边
            for (int j = i + 1; j < n; j++) {//右边

                //两个人都想使自己的分数与对方的分数的差值最小
                //如果只有两个元素时，那么两个人的最大得分差值应该是最大的那个值
                if (j - i == 1) res[i][j] = Math.max(stones[i], stones[j]);  //状态转移方程
                //如果多余两个元素时，两个人得分的最大差值应该是
                //左边的得分减去左边的最大差值，右边的得分减去右边的最大差值
                else res[i][j] = Math.max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1]);
            }
        }
        return res[0][n - 1]; //返回A能取的最大和
    }