原文链接: https://leetcode-cn.com/problems/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

中文题目

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

 

示例：

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。 

 

提示：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10 ^ 4

通过代码

高赞题解

思路

本题很明显要用记忆化搜索或者动态规划来求解，如果直接使用动态规划的话，我们要想清楚有哪些子状态需要存储。

首先一定要存储的是取到某一个位置时，已经得到的最大值或者后面能得到的最大值，但是光有位置是不够的，相同的位置有不同数量的堆可以取，所以我们还需存储当前的M值。

由于本题中的状态是从后往前递推的，如：假如最后只剩一堆，一定能算出来最佳方案，但是剩很多堆时不好算（依赖后面的状态）。所以我们选择从后往前递推。

递推公式

有了思路之后，我们就能很方便地定义dp数组了：

dp[i][j]表示剩余[i : len - 1]堆时，M = j的情况下，先取的人能获得的最多石子数

1. i + 2M >= len, dp[i][M] = sum[i : len - 1], 剩下的堆数能够直接全部取走，那么最优的情况就是剩下的石子总和
2. i + 2M < len, dp[i][M] = max(dp[i][M], sum[i : len - 1] - dp[i + x][max(M, x)]), 其中 1 <= x <= 2M，剩下的堆数不能全部取走，那么最优情况就是让下一个人取的更少。对于我所有的x取值，下一个人从x开始取起，M变为max(M, x)，所以下一个人能取dp[i + x][max(M, x)]，我最多能取sum[i : len - 1] - dp[i + x][max(M, x)]。

示例演示

对于piles = [2,7,9,4,4]，我们可以得到下图所示的dp数组，结果为dp[0][1]

是不是非常清晰呢

代码

有了递推公式之后，代码就很好写了：

[]
public int stoneGameII(int[] piles) {
    int len = piles.length, sum = 0;
    int[][] dp = new int[len][len + 1];
    for (int i = len - 1; i >= 0; i--) {
        sum += piles[i];
        for (int M = 1; M <= len; M++) {
            if (i + 2 * M >= len) {
                dp[i][M] = sum;
            } else {
                for (int x = 1; x <= 2 * M; x++) {
                    dp[i][M] = Math.max(dp[i][M], sum - dp[i + x][Math.max(M, x)]);
                }
            }
        }
    }
    return dp[0][1];
}

统计信息

通过次数	提交次数	AC比率
7078	10855	65.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言