1140. Stone Game II

Alice and Bob continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.  Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Example 2:

Input: piles = [1,2,3,4,5,100]
Output: 104

Constraints:

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 104

这道题是石头游戏系列的第二道,跟之前那道 Stone Game 不同的是终于换回了 Alice 和 Bob!还有就是取石子的方法,不再是只能取首尾两端的石子堆,而是可以取 [1, 2M] 范围内的任意X堆,M是个变化的量,初始化为1,每次取完X堆后,更新为 M = max(M, X)。这种取石子的方法比之前的要复杂很多,由于X的值非常的多,而且其不同的选择还可能影响到M值,那么整体的情况就特别的多,暴力搜索基本上是行不通的。这种不同状态之间转移的问题用动态规划 Dynamic Programming 是比较合适的,首先来考虑 DP 数组的定义,题目要求的是 Alice 最多能拿到的石子个数,拿石子的方式是按顺序的,不能跳着拿,所以决定某个状态的是两个变量,一个是当前还剩多少石子堆,可以通过当前位置坐标i来表示,另一个是当前的m值,只有知道了当前的m值,那么选手才知道能拿的堆数的范围,所以 DP 就是个二维数组,其 dp[i][m] 表示的意义在上面已经解释了。接下来考虑状态转移方程,由于在某个状态时已经知道了m值,则当前选手能拿的堆数在范围 [1, 2m] 之间,为了更新这个 dp 值,所有x的情况都要遍历一遍,即在剩余堆数中拿x堆,但此时x堆必须小于等于剩余的堆数,即 i + x <= n,i为当前的位置。由于每个选手都是默认选最优解的,若能知道下一个选手该拿的最大石子个数,就能知道当前选手能拿的最大石子个数了,因为二者之和为当前剩余的石子个数。由于当前选手拿了x堆,则下个选手的位置是 i+x,且m更新为 max(m,x),所以其 dp 值为 dp[i + x][max(m, x)])。为了快速得知当前剩余的石子总数,需要建立累加和数组,注意这里是建立反向的累加和数组,其中 sums[i] 表示范围 [i, n-1] 之和。分析到这里就可以写出状态状态转移方程如下:

dp[i][m] = max(dp[i][m], sums[i] - dp[i + x][max(m, x)])

接下来就是一些初始化和边界定义的问题需要注意的了,dp 数组大小为 n+1 by n+1,因为选手是可能一次将n堆都拿了,比如 n=1 时,所以 dp[i][n] 是存在的,且需要用 sums[i] 来初始化。更新 dp 时需要用三个 for 循环,分别控制i,m,和 x,注意更新从后往前遍历i和m,因为我们要先更新小区间,再更新大区间。x的范围要设定为 x <= 2 * m && i + x <= n,前面也讲过原因了,最后的答案保存在 dp[0][1] 中返回即可,参见代码如下:

解法一:

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> sums = piles;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = n - 2; i >= 0; --i) {
            sums[i] += sums[i + 1];
        }
        for (int i = 0; i < n; ++i) {
            dp[i][n] = sums[i];
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int m = n - 1; m >= 1; --m) {
                for (int x = 1; x <= 2 * m && i + x <= n; ++x) {
                    dp[i][m] = max(dp[i][m], sums[i] - dp[i + x][max(m, x)]);
                }
            }
        }
        return dp[0][1];
    }
};

我们再来用递归加记忆数组的方式来实现一下,其实核心思想跟上面完全一样,这里就不过多的讲解了,直接看代码吧:

解法二:

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> sums = piles;
        vector<vector<int>> memo(n, vector<int>(n));
        for (int i = n - 2; i >= 0; --i) {
            sums[i] += sums[i + 1];
        }
        return helper(sums, 0, 1, memo);
    }
    int helper(vector<int>& sums, int i, int m, vector<vector<int>>& memo) {
        if (i + 2 * m >= sums.size()) return sums[i];
        if (memo[i][m] > 0) return memo[i][m];
        int res = 0;
        for (int x = 1; x <= 2 * m; ++x) {
            int cur = sums[i] - sums[i + x];
            res = max(res, cur + sums[i + x] - helper(sums, i + x, max(x, m), memo));
        }
        return memo[i][m] = res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1140

类似题目:

Stone Game

参考资料:

https://leetcode.com/problems/stone-game-ii/

https://leetcode.com/problems/stone-game-ii/discuss/345247/C%2B%2B-DP-(Tabulation)

https://leetcode.com/problems/stone-game-ii/discuss/345230/JavaPython-DP-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation