------前言,要提的问题在下面------
这题我考虑先用记忆化搜索的方式解决,刚开始定义的递归函数定义得不好。
思路是这样的:先求出,在双方发挥最佳水平下,Alice 能取得石子的最大数量。用石子总数量减去这个最大数量得到的差,如果大于 0,说明 Alice 能赢得比赛。
这样定义出来的递归函数,参数不仅要有剩余石头的 「左边界」和「右边界」,还要有「剩余石子的数量」,要记忆的空间特别大。用 Map 来记忆化,一提交,耗时 1964 ms,勉强通过。后来再次尝试提交,超时。
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int sum = accumulate(piles.cbegin(), piles.cend(), 0);
int a = alice(piles, 0, piles.size() - 1, sum);
return a > sum - a;
}
private:
map<vector<int>, int> a;
map<vector<int>, int> b;
// alice 从 piles[lo...hi] 中取石头所能得到的最大总数,双方都发挥出最佳水平
int alice(const vector<int> &piles, int lo, int hi, int sum) {
if (lo > hi) {
return 0;
}
if (a.find({ lo, hi, sum }) != a.cend()) {
return a[{ lo, hi, sum }];
}
return a[{ lo, hi, sum }] = max(sum - bob(piles, lo + 1, hi, sum - piles[lo]),
sum - bob(piles, lo, hi - 1, sum - piles[hi]));
}
// bob 从 piles[lo...hi] 中取石头所能得到的最大总数,双方都发挥出最佳水平
int bob(const vector<int> &piles, int lo, int hi, int sum) {
if (lo > hi) {
return 0;
}
if (b.find({ lo, hi, sum }) != b.cend()) {
return b[{ lo, hi, sum }];
}
return b[{ lo, hi, sum }] = max(sum - alice(piles, lo + 1, hi, sum - piles[lo]),
sum - alice(piles, lo, hi - 1, sum - piles[hi]));
}
};
于是,我绞尽脑汁,想着怎样定义一个好的递归函数,才不用记忆像「剩余石子的数量」这种这么大范围的参数。
没思路,于是就参考了老师代码仓库中的代码,主要看了 main.cpp 。
研究了几十分钟,还是不太明白函数的定义,主要没搞懂函数 play() 实现里的加法、减法是怎么得来的。
但此时有了自己的想法,我就试着按照自己的思路写了下:
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int n = piles.size();
memo = vector<vector<vector<int>>>(2, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
return play(piles, 0, piles.size() - 1, 0) > 0;
}
private:
vector<vector<vector<int>>> memo;
// 从剩下的 piles[lo...hi] 中取石子,当前选手与另一个选手的石子数量之差的最大值,每位选手都发挥出最佳水平
int play(const vector<int> &piles, int lo, int hi, int player) {
if (lo == hi) {
return piles[lo];
}
if (memo[player][lo][hi] != INT_MIN) {
return memo[player][lo][hi];
}
return memo[player][lo][hi]= max(-play(piles, lo + 1, hi, 1 - player) + piles[lo],
-play(piles, lo, hi - 1, 1 - player) + piles[hi]);
}
};
问题:
return true
通过。