题目：石子游戏 II

  • 亚历克斯和李继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子piles[i]。游戏以谁手中的石子最多来决出胜负。
  • 亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
  • 在每个玩家的回合中，该玩家可以拿走剩下的前X堆的所有石子，其中1 <= X <= 2M。然后，令M = max(M, X)。
  • 游戏一直持续到所有石子都被拿走。
  • 假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
示例：
  1. 输入：piles = [2,7,9,4,4]
  2. 输出：10
  3. 解释：
  4. 如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
  5. 如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
  6. 所以我们返回更大的 10。
提示：
  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

来源：力扣（LeetCode）第1140题

链接：https://leetcode-cn.com/problems/stone-game-ii

分析：

  • 这道题可以采用递归加记忆化搜索的方式进行。
  • 我们需要穷举出所有的状态。
  • 由于重复计算的地方太多，所以使用记忆化搜索，也可以说使用了动态规划。

代码：

  1. class Solution {
  2.     int len;
  3.     int[] sum;int[][] dp;
  4.     public int stoneGameII(int[] piles) {
  5.         dp = new int[150][150]; // dp数组用来存放算过的值。
  6.         len = piles.length;
  7.         sum = new int[len+1];
  8.         // 求第i个数到最后的总和。
  9.         for (int i = len - 1; i >= 0; i--) sum[i] = sum[i+1] + piles[i];
  10.         return dfs(0, 1);
  11.     }
  12.     // 返回从第i个石子堆开始，M为m的最优情况。
  13.     public int dfs(int i, int m) {
  14.         if (dp[i][m] != 0) return dp[i][m]; // 如果i，m已经算过了，不用再算了。
  15.         if (i >= len) return 0; // i超出数组下标，也不用再算了，这是递归的基线条件。
  16.         if (i + 2 * m >= len) return sum[i]; // 特殊情况，如果剩下的石子堆可以一次拿完，那么肯定全拿了。
  17.         int best = 0; // 存放最优情况
  18.         for (int x = 1; x <= 2 * m; x++) 
  19.             /*
  20.                 如果i之前的石子堆被拿完，那么首先判断在这1-2*m次里Alex能拿到最大的情况是哪次。
  21.                 于是我们穷举每一次情况，找出最大的情况。
  22.                 每一次情况中，我们看从第i堆石子到最后。i + x，也就是你从i开始拿x堆石子，之间的总和。
  23.                 然后还要加上从i+x+1到最后你拿的最优情况，就是值最大的情况。
  24.                 因此，我们减去Lee的最优情况，因为Lee也会取最优，得到的就是Alex的情况。
  25.             */
  26.             best = Math.max(best, sum[i] - dfs(i + x, Math.max(m, x)));
  27.         dp[i][m] = best;
  28.         return best;
  29.     }
  30. }