题目：石子游戏 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。 

提示：

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

来源：力扣（LeetCode）第1140题

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

分析：

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

代码：

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