【每日一题Day126】LC1140石子游戏Ⅱ | 博弈dp 记忆化搜索

石子游戏Ⅱ【LC1140】

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

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

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

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

就是说还挺难的

记忆化搜索+dp

• 思路：使用记忆化搜索每个可能的状态，并记录至dp数组中，定义dfs(i,m) 表示从piles[i]开始取石子，每次最多取2∗m堆石子，可以获得的最大石子数量

    那么dfs(0,1) 即为最终结果

• 如何求得可以获得的最大石子数量？

    对于每个节点，由于剩余的石子总数是固定的，如果拿了某几堆石子后，对手能得到的石子数最少，那么自己能得到的石子数就是最多的。【保证每位选手发挥出最佳水平】

• 为了方便求出剩余石子的总数，可以记录在后缀和数组中
  
• 在搜索过程中，会遇到重复的状态，因此可以记录至dp数组中，再次遇到这个结果时，直接从dp数组中获取
  
• 实现
• 首先预处理后缀和数组s[i]：表示[i,n−1]堆石子总数
• 递归函数设计：
• 参数：当前石堆序号i，截止目前可以一次取的最大数量m，每次最多可以取得2m堆
• 返回值：int 能够取得的最大石子数量
  
• 什么时候返回：已经搜索过该状态时返回dp[i][m]，剩余石堆全部可以取完时，返回s[i]
• 递归逻辑

    本轮取x∈[1,2m]堆石子时，对方从第i+x堆石子开始取 ，能够取的最大石子数量为dfs(i+x,max(m,x))，那么我方能取最多的石子数量为s[i]−min(dfs(i+x,max(x,m)))

class Solution {
    int[] s;
    int[][] dp;
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        s = new int[n];
        dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--){
            s[i] = piles[i] + (i + 1 < n ? s[i + 1] : 0);
            Arrays.fill(dp[i], -1);
        }
        return dfs(0, 1);
    }
    public int dfs(int i, int m){
        if (i + m * 2 >= s.length) return s[i];
        if (dp[i][m]!= -1) return dp[i][m];
        int min = Integer.MAX_VALUE;
        for (int x = 1; x <= 2 * m; x++){
            min = Math.min(min, dfs(i + x, Math.max(x, m)));
        }
        dp[i][m] = s[i] - min;
        return dp[i][m];
    }
}

复杂度

• 时间复杂度：O(n3)，状态个数为O(n2)，单个状态计算的时间复杂度为O(n)
• 空间复杂度：O(n2)
• 优化：减小dp数组的内存，m的最大值为⌊n+1/4⌋

如果每次都拿满2m堆，那么最后有

4M-2 是看下一次拿的能不能小于 n，递归过程没有记录递归边界

转化为动态规划

• 动态规划

1. 确定dp数组（dp table）以及下标的含义

dp[i][m]表示考虑区间为[i,n−1]时，一次性可以取走的石头堆数最大为2m，在双方都做最好选择的情况下，可以获得的最大石子数量。

    那么dp[0][1]即为可以拿到的石子最大数量。

2. 确定递推公式

• 当剩余石头堆数小于等于2m时，直接取完
• 但剩余石头数大于2m时，枚举本次可以取石子的堆数为x∈[1,2m]，本次最大数量取决于dp[i+x][max(m,x)]的最小值

3. dp数组如何初始化
   无需初始化，在递推时消化
   
4. 确定遍历顺序倒序遍历piles，正序遍历右端点

• 为什么？
  在记忆化搜索中，我们从起点 (0,1)出发向下「递」，此时 i不断变大；「归」就是从叶子出发向着起点计算，此时 i不断变小。所以要改成递推（只有「归」），i必须从大到小计算。对于 M来说正序逆序都可以，因为我们是从f[i+x][]转移来的，无论先算哪个 M 都是正确的

5. 举例推导dp数组
   

dp数组的第二维度->最大为⌊n/2⌋+1

class Solution {
    public int stoneGameII(int[] piles) {
        int s = 0, n = piles.length;
        // int[][] f = new int[n][n + 1];
        int[][] f = new int[n][n/2 + 2];
        for (int i = n - 1; i >= 0; --i) {
            s += piles[i];
            for (int m = 1; m <= i / 2 + 1; ++m) {
                if (i + m * 2 >= n) f[i][m] = s;
                else {
                    int mn = Integer.MAX_VALUE;
                    for (int x = 1; x <= m * 2; ++x)
                        mn = Math.min(mn, f[i + x][Math.max(m, x)]);
                    f[i][m] = s - mn;
                }
            }
        }
        return f[0][1];
    }
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/stone-game-ii/solutions/2125753/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-jjax/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度

• 时间复杂度： O(n3)，状态个数为O(n2)，单个状态计算的时间复杂度为O(n)
• 空间复杂度：O(n2)