当前位置：首页 > article >正文

【C++前缀和动态规划博弈】1140. 石子游戏 II|2034

article 2024/11/19 19:46:04

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
C++动态规划
博弈：往往后续状态已知，前续状态未知

LeetCode1140. 石子游戏 II

Alice 和 Bob 继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
Alice 和 Bob 轮流进行，Alice 先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设 Alice 和 Bob 都发挥出最佳水平，返回 Alice 可以得到的最大数量的石头。
示例 1：
输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始 Alice 取了一堆，Bob 取了两堆，然后 Alice 再取两堆。Alice 可以得到 2 + 4 + 4 = 10 堆。
如果 Alice 一开始拿走了两堆，那么 Bob 可以拿走剩下的三堆。在这种情况下，Alice 得到 2 + 7 = 9 堆。返回 10，因为它更大。
示例 2:
输入：piles = [1,2,3,4,5,100]
输出：10⁴
提示：
1 <= piles.length <= 100
1 <= piles[i] <= 10⁴

错误解法：动态规划+前缀和

N = piles ，2M大于n没意义，所以本题假定其小于等于n。

动态规划的状态表示

m为当前可以移除的石子数量，i为已经移除石头堆数。
dp0[i][m] 表示,当前行动者是Alice，Alice最小分数。
dp1[i][m] 表示当前行动者是Bom，Alice的最大分数。
空间复杂度：O(nM)

动态规划的转移方程

枚举前置状态dp0[i][m]，令 Alice移除了x块石头，1 <= x ,i+x <= N
m1 = max(m,2x)
MaxSelf(dp1[i+x][m1],preSum[i+x]- dp0[i][m])
单个状态时间复杂度O(n)，总时间复杂度：O(nMn)
枚举前置状态dp1，类似。

动态规划的填表顺序

i,m,x 从小到大

动态规划的初始值

			const int iNotMay = 1e8;
			vector<vector<int>> dp0(N + 1, vector<int>(N + 1, iNotMay));
			vector<vector<int>> dp1(N + 1, vector<int>(N + 1,- iNotMay));
			dp0[0][min(2,N)] = 0;
			正负iNotMay 表示	非法。转移时忽略非法数据。

动态规划的返回值

max(dp0.back().back(),preSum.back()-dp1.back().back())

错误原因

{1,2,3} Alice 选择{1} Bob 选择{2} Alice选择 {3}
实际上：Bob 选择 {2,3}

错误代码

class Solution {
		public:
			int stoneGameII(vector<int>& piles) {
				vector<int> preSum(1);
				for (const auto& n : piles) {
					preSum.emplace_back(n + preSum.back());
				}
				const int N = piles.size();
				const int iNotMay = 1e8;
				vector<vector<int>> dp0(N + 1, vector<int>(N + 1, iNotMay));
				vector<vector<int>> dp1(N + 1, vector<int>(N + 1,- iNotMay));
				dp0[0][min(2,N)] = 0;
				for (int i = 0; i <= N; i++) {
					for (int m = 1; m <= N; m++) {
						if (dp0[i][m] < iNotMay) {
							for (int x = 1; (x <= m )&&(i + x <= N); x++) {
								int m1 = max(m, 2 * x);
								m1 = min(m1, N);
								dp1[i + x][m1] = max(dp1[i + x][m1], preSum[i + x] - preSum[i] + dp0[i][m]);
							}
						}
						if (dp1[i][m] >= 0) {
							for (int x = 1; (x <= m) && (i + x <= N); x++) {
								int m1 = max(m, 2 * x);
								m1 = min(m1, N);
								dp0[i + x][m1] = min(dp0[i + x][m1], dp1[i][m]);
							}
						}
					}
				}
				int i1 = *std::max_element(dp1.back().begin(), dp1.back().end());		
				for (const auto& n : dp0.back()) {
					if (iNotMay == n) { continue; }
					i1 = max(i1, n);
				}
				return i1;
			}
		};

动态规划+前缀和

动态规划的状态表示

dp[i]][m] 当前行动者可以选择[1,m]堆石子，已经选择了i堆，当前行动者从剩余的石子中能获得的最大分数。

动态规划的转移方程

后续状态已知，前置状态未知。
枚举前置状态，枚举需求了x堆石头。 1 <= x <= m 且 i+x <= N
dp[i][m] = max(preSum[i+x]-dp[i+x][m1])

动态规划的填表顺序

i从N-1到0，m从1到N , x从1到m

动态规划的初始值

dp[N].assign(N,0)

动态规划的返回值

dp[0][min(2,N)]

代码

核心代码

class Solution {
		public:
			int stoneGameII(vector<int>& piles) {
				vector<int> preSum(1);
				for (const auto& n : piles) {
					preSum.emplace_back(n + preSum.back());
				}
				const int N = piles.size();
				vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
				for (int i = N - 1; i >= 0; i--) {
					for (int m = 1; m <= N; m++) {
						int& cur = dp[i][m];
						for (int x = 1; (x <= m) && (i + x <= N); x++) {
							int m1 = max(2 * x, m);
							m1 = min(m1, N);
							cur = max(cur, preSum.back() - preSum[i] - dp[i + x][m1]);
						}

					}
				}			
				return dp[0][min(2,N)];
			}
		};

单元测试

	vector<int> piles;
		TEST_METHOD(TestMethod1)
		{
			piles = { 1};
			auto res = Solution().stoneGameII(piles);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod2)
		{
			piles = { 1,2 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod3)
		{
			piles = { 1,2,3 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod4)
		{
			piles = { 1,2,3,4 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod11)
		{
			piles = { 2, 7, 9, 4, 4 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod12)
		{
			piles = { 1,2,3,4,5,100 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(104, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功