题目链接

石子游戏 II

题目描述

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 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。

思路

• 动态规划状态定义

  记 $n$ 为输入 $piles$ 的长度，即石子堆的个数，定义一个 $n \times n$ 的二维 $dp$ 数组，其中 $dp[i][j]$ 代表当剩下的石子堆为 $piles[i…n - 1]$ 且 $M = j$ 时当前玩家能拿到的最大石子数目。

• 状态方程

  根据上述 $dp$ 数组的定义，可以得到状态方程的定义如下：

  记 $sum$ 为当前剩下的石子堆的总石子数目，则当 $M = j$ 时，当前玩家可以选择从最左边开始拿走 $x$ 堆石子，其中 $1 \leq x \leq 2M$ ，因此他能获得的最大石子数目 = $sum$ - 另一个人按照最优策略能拿到的最大石子数目。

  因此状态转移方程如下：

  for (int x = 1; x <= 2 * M; x++) {
      dp[i][M] = max(dp[i][M], sum - dp[i + x][max(x, M)]);
  }
  

• base case

  如果当前可以拿的最大石子堆数目（即 $2M$）大于剩下的石子堆数目，则最大得分即为剩下的石子数，因此base case即为：

  if (i + 2 * M >= n) {
      dp[i][j] = sum;
  }
  

• c++代码

  明确状态定义，状态方程和base case后，可以写出如下c++代码：

  class Solution {
      public:
          int stoneGameII(vector<int>& piles) {
              int sum = 0, n = piles.size();
              // dp[i][j] means maximum score the current player can get
              // when M == j and there are stones piles[i...n - 1] left
              vector<vector<int>> dp(n, vector(n, 0));
              for (int i = n - 1; i >= 0; i--) {
                  sum += piles[i];
                  for (int j = 0; j < n; j++) {
                      // base case
                      if (i + 2 * j >= n) {
                          dp[i][j] = sum;
                          continue;
                      }
                      for (int x = 1; x <= 2 * j; x++) {
                          dp[i][j] = max(dp[i][j], sum - dp[i + x][max(x, j)]);
                      }
                  }
              }
              return dp[0][1];
          }
  };
  

• 几个细节：

  • $dp$ 数组到底应该定义为 $n \times n$ 还是 $(n + 1) \times (n + 1)$呢？

    我看别人用这个思路定义的 $dp$ 数组都是 $(n + 1) \times (n + 1)$ 的，但是我定义成 $n \times n$ 也AC了，因此感觉还是得看题目来。

    但说实话刷题刷到现在自己也没有真正弄清这个小细节，导致每次动手写代码的时候老是很纠结，这里先写一下目前自己的理解，如果后续有更深刻更正确的理解我会再记录一下。

    总的来说，应该两者都没问题，就是看哪个用起来方便了（主要针对 $dp$ 数组与原数组的下标索引不一致的问题），是由你定义的状态的base case来定的。

    有的题的base case强调一个与0有关的状态，比如数组的前缀和中，前0个元素的和为0，前1个元素的和才是数组的第一个元素，即 $nums[0]$ 。这种情况下，开一个 $n + 1$ 的 $dp$ 数组就会比较方便。

    而这个题目中并没有强调一个与0有关的状态，事实上，根本没用到什么如果当前剩下的石子堆为第0堆到第n - 1堆时……的状态，最边界的情况也只是第1堆到第n - 1堆，只不过这个第1堆的索引为0罢了。因此定义一个 $n \times n$ 的二维数组就够用了。

    总之如果定义数组的“边长”为 $n + 1$ 的话，需要考虑 $dp$ 数组与原数组下标索引不一致的问题：因为这种时候往往 $dp[0]/dp[0][0]$ 为base case，因此循环遍历计算 $dp$ 数组时的索引往往是从1开始的，此时代码往往长这样：

    dp[i] = ...nums[i - 1]...
    

    而如果定义数组的“边长”为 $n$ 的话就没有这个问题。

    所以具体怎么定义还是看题目吧，实在不确定的话就先定义成 $n \times n$ ，如果发现不行（如无法覆盖base case等情况）的话再换成 $(n + 1) \times (n + 1)$ 也一样。

  • 为什么这里base case的判断条件中是 i + 2 * j >= n 而不是 i + 2 * j >= n - 1 呢？$piles$ 的最大索引不是 $n - 1$ 吗？

    这个其实用几个具体的数组代入再稍微思考一下就会发现应该是前者：

    比如假设总共有三堆石子，然后现在 $i = 0, j = 1$，也就是说现在还剩三堆石子没拿，当前玩家最多可以拿 $2 * j = 2$ 堆石子。

    如果判断条件是后者的话这个 $if$ 判断会返回 $true$ ，意思就是说这是个base case，而根据base case的定义，也就是说当前玩家可以把剩下的石子堆全拿走，但是显然这个是不对的，因为还剩三堆但是最多只能拿两堆啊！但如果判断条件是前者的话就不会犯这个错误。

    为什么呢？首先我们要搞清楚 i + 2 * j 的含义，它的含义是说：我从第 $i$ 堆石子开始，总共拿了 $2 * j$ 堆石子后，下一个人接着开始拿时，剩下的石子堆的最小索引。

    所以如果只是 >= n - 1 的话说明下一个人还可以从 piles[n - 1] 这堆石子开始拿，说明当前玩家还不能把剩下的石子都拿走。

    但如果是 >= n 的话说明下一个人只能从 piles[n] 这堆石子开始拿了，但是 piles[n] 不存在，也就是说下一个人没有石子可拿了，即当前玩家可以把剩下的石子都拿走。