LC-1140.石子游戏II

题目描述

leetcode 中等题

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

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

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

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

假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

示例1：

输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。

提示1：

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

动态规划

设 $dp[i][j]$ 表示从第 $i$ 个数开始选，当前 $M$ 为 $j$ 情况下能取到的最多石子数，那么 $dp[0][1]$ 为答案。

对于每个 $dp[i][j]$ ，设当前剩余石头数为 $suf[i]$，我们枚举当前能选的石堆数量 $1…2*j$ ，设当前枚举到 $k$ ，那么因为

爱丽丝和鲍勃都发挥出最佳水平

所以鲍勃在爱丽丝做出某个选择后能取到的最大石头数为 $dp[i + k][Math.max(k, m)]$ ，也就是说爱丽丝能取到的石头数为 $suf[i] - dp[i + k][Math.max(k, m)]$ ，为了使石子数最多，我们取最大值即可。

$$
\begin{align}
&dp(i,j) = max(suf[i] - dp[i + k][Math.max(k, m)])　　　　　　　　　　　　　　 1 <= k <= 2*m\\
\end{align}
$$

class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] suf = new int[n + 1];
        for(int i = n - 1; i >= 0; i--){
            suf[i] = suf[i + 1] + piles[i];
        }
        int[][] dp = new int[n + 1][2 * n];
        for(int i = n - 1; i >= 0; i--){
            for(int m = 1; m < 2 * n; m++){
                if(i + m * 2 >= n){
                    dp[i][m] = suf[i];
                    continue;
                }
                int min = Integer.MAX_VALUE;
                for(int k = 1; k <= m * 2; k++){
                    min = Math.min(min, dp[i + k][Math.max(k, m)]);
                }
                dp[i][m] = suf[i] - min;
            }
        }
        return dp[0][1];
    }
}