1140. 石子游戏 II

题目链接：1140. 石子游戏 II

方法一：dfs（超时）

解题思路

• 题目要求\(Alice\)取得的石子数尽可能的多，那么就要使得\(Bob\)取得的石子尽可能的少，但是\(Bob\)也想要取得更多的石子，因此\(Alice\)在每次选取时，要使得在此种选取方法下，\(Bob\)能取的石子数最小。
• 现定义\(dfs(idx, m)\)表示从\(piles[idx]\)开始拿，\(M = m\)时，能够取得的最大石子数量；初始化\(piles\)数组为后缀和数组\(s\)，\(s[i] = \sum_{j=i}^{n-1}piles[j]\)。
• 由于从当前\(idx\)开始取，石子的总和为\(s[idx]\)，\(那么当前能取得的最大值 = s[idx] - 当前操作之后能取得的最大值中的最小值\)，即\(dfs(idx, m) = s[idx] - min_{x=1}^{2m}dfs(idx+x, max(m, x))\)。
• \(结果为dfs(0, 1)\)。

代码

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        for (int i = n - 2; i >= 0; i -- ) piles[i] += piles[i + 1];
        function<int(int, int)> dfs = [&](int idx, int m) -> int { // function类模板 + lambda表达式
            if (idx + 2 * m >= n) return piles[idx]; // 若可以一次拿走剩余所有石堆，则返回剩余所有石子数量
            int mi = INT_MAX;
            for (int x = 1; x <= 2 * m; x ++ ) mi = min(mi, dfs(idx + x, max(x, m)));
            return piles[idx] - mi;
        };
        return dfs(0, 1);
    }
};

方法二：记忆化搜索优化dfs

解题思路

由于在递归的过程中会多次求相同的\(dfs(i, m)\)的值，那么为了使得每一种\(dfs(i, m)\)只求一次，那么可以使用数组\(f[i][m]\)存取相应的值，再次遇到时直接取值返回即可。

代码

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        for (int i = n - 2; i >= 0; i -- ) piles[i] += piles[i + 1];
        int f[n][(n + 1) / 4 + 1];
        memset(f, -1, sizeof(f));
        function<int(int, int)> dfs = [&](int idx, int m) -> int { // function类模板 + lambda表达式
            if (idx + 2 * m >= n) return piles[idx]; // 若可以一次拿走剩余所有石堆，则返回剩余所有石子数量
            int &res = f[idx][m];
            if (res != -1) return res;
            int mi = INT_MAX;
            for (int x = 1; x <= 2 * m; x ++ ) mi = min(mi, dfs(idx + x, max(x, m)));
            res = piles[idx] - mi;
            return res;
        };
        return dfs(0, 1);
    }
};

复杂度分析

时间复杂度：\(O(n^3)\)，单个状态的计算时间为\(O(n)\)，状态个数为\(O(n^2)\)；
空间复杂度：\(O(n^2)\)。

方法三：dp

解题思路

舍去递归中“递”的过程—向下，直接从“归”—向上着手。

代码

class Solution {
public:
    int stoneGameII(vector<int> &piles) {
        int s = 0, n = piles.size(), f[n][n + 1];
        for (int i = n - 1; i >= 0; --i) {
            s += piles[i];
            for (int m = 1; m <= i / 2 + 1; ++m) { 
                // 当选取到i时，m可能取得值的范围。每次x可以取的值都为1，或则为2m，两种极端情况下m的范围。
                if (i + m * 2 >= n) f[i][m] = s;
                else {
                    int mn = INT_MAX;
                    for (int x = 1; x <= m * 2; ++x)
                        mn = min(mn, f[i + x][max(m, x)]);
                    f[i][m] = s - mn;
                }
            }
        }
        return f[0][1];
    }
};

复杂度分析

同方法二

详情参考：灵茶-教你一步步思考动态规划！