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

本文涉及的基础知识点

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);}

扩展阅读

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

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。