题目链接：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];
}
};
复杂度分析
同方法二
详情参考：灵茶-教你一步步思考动态规划！