我尝试使用昨天猫鼠游戏的思路来解决这个博弈问题，也就是DFS
private:
int alice, bob;// 用来分别计数两人手上的石子数量
public:
bool dfs(vector<int>& piles, int start, int end, bool firstTurn) {
// 用两个指针来标记剩余石子堆的起始/结束位置
// 出口条件是：石子选完了，双方手上石子数量的情况
if (start > end) {
// 当石子都选完了
if (alice > bob) return true;// alice手上石子更多则alice赢
else return false;// 否则bob赢
}
// 模拟取石子的情况
if (firstTurn) {
// 从头取
alice += piles[start];
// 可达必败则必胜
if (!dfs(piles, start + 1, end, !firstTurn))return true;
alice -= piles[start];
// 从头取
alice += piles[end];
// 可达必败则必胜
if (!dfs(piles, start, end - 1, !firstTurn))return true;
alice -= piles[end];
}
else {
// 从头取
bob += piles[start];
// 可达必败则必胜
if (!dfs(piles, start + 1, end, !firstTurn))return false;
bob -= piles[start];
// 从头取
bob += piles[end];
// 可达必败则必胜
if (!dfs(piles, start, end - 1, !firstTurn))return false;
bob -= piles[end];
}
return false;
}
bool stoneGame(vector<int>& piles) {
// 两人分别从首位选取一堆石子，最后手上最多的赢
// 可达必败则必胜
// 只达必胜则必败
// alice赢指的是alice必胜态，也就是说有可能赢就行
// 那么bob赢就是指必败态
return dfs(piles, 0, piles.size() - 1, true);
}
在不考虑超时的情况下，这段代码是可以通过题目的，如果要解决超时问题
- 思路1是通过记忆化优化DFS，GPT给出的是
memo[start][end][firstTurn]这样一个三维数组，我不是很理解，同时也觉得这过于复杂了 - 换个思路，使用动态规划
官解
官解中使用动态规划首先引入了一个概念：alice和bob手上石子数量的差值，因为如果想我上面那样有两个变量的话是没法动态规划的
动态规划三步走：
- dp数组的定义
dp[i][j]表示从i位置到j位置，差值的最大值
如果最大值小于0，则alice必输，retrun false，否则return true
等于0不存在，因为石子是奇数 - dp数组初始化
二维数组的行列数都是石子堆长度
当i<=j的时候dp[i][j]才是有意义的，于是对于i>j的情况都可以置0，不会对其他项产生影响
当i==j的时候，dp[i][j]只等于piles[i][j] - 状态转移方程
当前玩家可以从头/尾，即dp[i]和dp[j]中选择一个，并使得自己的石子数达到最大值
差值的最大值好理解，可是为什么是i位置到j位置呢？
bool stoneGame(vector<int>& piles) {
int len = piles.size();
vector<vector<int>> dp(len,vector<int>(len,0));
// 初始化dp数组
for (int i = 0; i < len; i++) dp[i][i] = piles[i];
// 注意这边的递推方向，i是从后往前，j是从前往后
// i从len-2开始，[len-1][len-1]已经被初始化了，其他的[len-1][j]都是没有意义的
for (int i = len-2; i >=0; i--) {
// j>i才有意义
for (int j = i+1; j < len; j++) {
// 为什么这里是-可能的最大值？
// 减去的是对方可能的最大值，也就是自己先手，对方后手的最大值
dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1]);
}
}
return dp[0][len - 1] > 0;
}
空间优化不是很看得懂，下次再说