1872-石子游戏 VIII(Stone Game VIII)
发表于：2021-12-03 | 分类： 困难
字数统计: 2.2k | 阅读时长: 10分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/stone-game-viii

英文原文

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:

  1. Choose an integer x > 1, and remove the leftmost x stones from the row.
  2. Add the sum of the removed stones' values to the player's score.
  3. Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.

 

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

 

Constraints:

  • n == stones.length
  • 2 <= n <= 105
  • -104 <= stones[i] <= 104

中文题目

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

  1. 选择一个整数 x > 1 ，并且 移除 最左边的 x 个石子。
  2. 将 移除 的石子价值之 和 累加到该玩家的分数中。
  3. 将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。

当只剩下 一个 石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下，Alice 和 Bob 的 分数之差 。

 

示例 1：

输入：stones = [-1,2,-3,4,-5]
输出：5
解释：
- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。

示例 2：

输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。

示例 3：

输入：stones = [-10,-12]
输出：-22
解释：
- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。

 

提示：

  • n == stones.length
  • 2 <= n <= 105
  • -104 <= stones[i] <= 104

通过代码

高赞题解

核心思路

通过理解题意，不难发现，当取走左边若干个石子后，对右边石子原来的分数是没有影响的，仍是前缀和，所以预处理一个前缀和是很显然的。

int[] sum = new int[n + 1];
for(int i = 0; i < n; i++) { 
  sum[i + 1] = sum[i] + stones[i];
}

游戏过程我们不妨先不考虑时间的要求，直接通过暴力模拟来解决。

暴力法

暴力法直接模拟游戏过程，需要注意每一轮得到的结果都是这一轮的玩家期望得分差值的最大值。如果当前已经取到第i (1 <= i <= n)块石子，那么这一轮可以取到的结果solve(i)就是从i到n中选择一个位置j，使得sum[j] - (下一轮对手的得分)最大，这里的sum[j]就是这一轮的得分，由于要保证双方均采用最优策略，下一轮对手也会选择最大的得分差值，所以相当于求解sum[j] - solve(j + 1)的最大值。

暴力法代码

class Solution {

    int n;
    int[] stones;
    int[] sum;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        sum = new int[n + 1];
        
        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];

        return solve(2);
    }

    public int solve(int idx){
        if(idx == n) return sum[idx];

        int res = sum[n];
        for(int i = idx; i < n; i++){
            res = Math.max(res, sum[i] - solve(i + 1));
        }
        return res;
    }
}

记忆化递归O(N ^ 2)

完全模拟达到指数级别的时间复杂度，肯定需要进行优化，递归加优化最常见的就是加一个备忘录，写成记忆化递归。

O(N ^ 2)递归代码

class Solution {

    int n;
    int[] stones;
    int[] sum;
    Integer[] memo;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        
        memo = new Integer[n + 1];
        sum = new int[n + 1];

        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
        memo[n] = sum[n];
        return solve(2);
    }

    public int solve(int idx){
        if(memo[idx] != null) return memo[idx];

        int res = sum[n];
        for(int i = idx; i < n; i++){
            res = Math.max(res, sum[i] - solve(i + 1));
        }
        return memo[idx] = res;
    }
}

记忆化过程还是很简单的，直接加个备忘录就可以了，不过这样还是O(N ^ 2)的时间复杂度，还是会超时的。

优化DP

在记忆化中，每次递归都要从当前位置向后遍历找到最大的满足条件的值，时间消耗较大，而每个位置都只与他后边的值有关，我们不妨来看一下solve(x)的值到底等于什么。

solve(x) = max(sum[x] - solve(x + 1), sum[x + 1] - solve(x + 2), … , sum[n - 1] - solve(n), sum[n] - solve(n + 1))

而后边这一段max(sum[x + 1] - solve(x + 2), ... , sum[n - 1] - solve(n), sum[n] - solve(n + 1))，恰好是solve(x + 1)的值，带入也就得到

solve(x) = Math.max(solve(x + 1), sum[x] - solve(x + 1))

这样我们就可以得到优化到O(N)时间复杂度的代码了

O(N)递归代码

class Solution {

    int n;
    int[] stones;
    int[] sum;
    Integer[] memo;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        
        memo = new Integer[n + 1];
        sum = new int[n + 1];

        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
        memo[n] = sum[n];
        return solve(2);
    }

    public int solve(int idx){
        if(memo[idx] != null) return memo[idx];

        int res = Math.max(solve(idx + 1), sum[idx] - solve(idx + 1));
        return memo[idx] = res;
    }
}

当然递归可以完成，迭代也同样可以，不过迭代DP是自底向上求解，在这道题里也就是从dp[n]开始一直求到dp[2]，逆序递推即可

O(N)动态规划代码

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] sum = new int[n + 1];
        for(int i = 0; i < n; i++){
            sum[i + 1] = sum[i] + stones[i];
        }

        int[] dp = new int[n + 1];
        dp[n] = sum[n];

        for(int i = n - 1; i >= 2; i--){
            dp[i] = Math.max(dp[i + 1], sum[i] - dp[i + 1]);
        }
        return dp[2];
    }
}

可以发现dp[i]只与dp[i + 1]有关，经典的空间优化，用一个变量代替dp数组即可

O(N)动态规划优化空间代码

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] sum = new int[n + 1];
        for(int i = 0; i < n; i++){
            sum[i + 1] = sum[i] + stones[i];
        }

        int res = sum[n];

        for(int i = n - 1; i >= 2; i--){
            res = Math.max(res, sum[i] - res);
        }
        return res;
    }
}

感谢@justfun的补充，前缀和计算时也只与相邻的前缀和相关，使用一个变量可以将代码空间复杂度优化为O(1)

动态规划 时间复杂度O(N),空间复杂度O(1) 代码

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += stones[i];
        }

        int res = sum;

        for(int i = n - 1; i >= 2; i--){
            sum -= stones[i];
            res = Math.max(res, sum - res);
        }
        return res;
    }
}

总结

博弈论的问题也做过几道了，还是不太能抓得住要领，不过这种优化DP的方法还是很值得学习的，希望可以学到更多东西。
如果文章有写的不对的地方，还请指出，感谢相遇~~

统计信息

通过次数 提交次数 AC比率
2187 3552 61.6%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
动态规划 数组 前缀和 数学 博弈
上一篇:
1870-准时到达的列车最小时速(Minimum Speed to Arrive on Time)
下一篇:
1893-检查是否区域内所有整数都被覆盖(Check if All the Integers in a Range Are Covered)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo