力扣-877-石子游戏

我尝试使用昨天猫鼠游戏的思路来解决这个博弈问题，也就是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. 思路1是通过记忆化优化DFS，GPT给出的是memo[start][end][firstTurn]这样一个三维数组，我不是很理解，同时也觉得这过于复杂了
2. 换个思路，使用动态规划

官解

官解中使用动态规划首先引入了一个概念：alice和bob手上石子数量的差值，因为如果想我上面那样有两个变量的话是没法动态规划的

动态规划三步走：

1. dp数组的定义
   dp[i][j]表示从i位置到j位置，差值的最大值
   如果最大值小于0，则alice必输，retrun false，否则return true
   等于0不存在，因为石子是奇数
2. dp数组初始化
   二维数组的行列数都是石子堆长度
   当i<=j的时候dp[i][j]才是有意义的，于是对于i>j的情况都可以置0，不会对其他项产生影响
   当i==j的时候，dp[i][j]只等于piles[i][j]
3. 状态转移方程
   当前玩家可以从头/尾，即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;
	}

空间优化不是很看得懂，下次再说