DP 博弈策略Game Strategy全解析Interview_DS_Algo 仓库 DP/Game Strategy 专题实战指南【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo导读本文以仓库 DP/Game Strategy 目录为研究对象系统讲解算法面试中高频的「对抗性动态规划Adversarial DP / Optimal Game Strategy」题型两名玩家轮流取数、各自最优决策、最终比较得分。你将掌握这类问题的统一建模思路递归 记忆化 → 自底向上递推、四种典型变体区间取端、区间切分、受限窗口、取模计数的解法骨架以及配套的复杂度分析与刷题路线全部内容均有本仓库对应源码可对照验证。一、专题定位这套题在考什么DP/Game Strategy目录下共收录了 10 个实现文件覆盖 LeetCode 与 GfG 上从 Easy 到 Hard 的经典博弈题。从 README.md 的题目清单看核心脉络非常清晰问题出处核心考点Optimal Strategy For A GameGfG区间 DP 基础模板取两端Predict the Winner.cppLeetCode 486区间 DP 两种建模绝对得分 vs 分差Stone Game.cppLeetCode 877区间 DP 数学结论恒胜Stone Game II.cppLeetCode 1140状态带约束 M 的对抗 DPStone Game III.cppLeetCode 1406线性 DP一次可取 1~3 堆Stone Game V.cppLeetCode 1563区间切分 前缀和Stone Game VII.cppLeetCode 1690区间 DP得分 剩余和Stone Game VIII.cppLeetCode 1872前缀和 线性 DPStone Game IX.cppLeetCode 2029取模计数O(n) 数学题Maximum Number of Moves to Kill All Pawns.cppLeetCode 3283BFS 状态压缩 DPTSP 式博弈它们共享同一套思想内核却各自演化出不同的状态定义与转移方式——这正是面试中「一题多解、多题一法」的典型代表。二、思想内核最优对抗策略Minimax所有「轮流取数比得分」的博弈题都可以抽象为同一句话这句注释直接写在了 Stone Game.cpp 里当你行动时选自己能拿到的最大收益max当对手行动时假定他也会最优决策即你要承受最坏结果min。用递归语言描述就是当前玩家的收益 本回合得分 剩余局面中「对方最优玩法」下的最坏结果。max/min交替出现正是 Minimax极小极大思想在零和取数游戏中的落地。因此这类题的通用模板包含三要素局面状态通常用(l, r)表示当前剩余的区间复杂题目追加额外维度玩家编号、可用步数 M 等递归转移枚举当前玩家的每一种合法动作取「本步收益 递归结果」的最值记忆化用二维或多维表缓存已算过的局面将指数级递归降为多项式复杂度。三、基础模板区间两端取数3.1 建模一直接求「最大绝对得分」Optimal Strategy For A GameGfG与 Predict the Winner.cpp 的 Approach-1 采用最直观的写法int solve(vectorint nums, int l, int r) { if(l r) return 0; // 无可取 if(l r) return nums[l]; // 只剩一个直接拿 // 取左端nums[l] 对手最优后剩下的最坏情况 int take_left nums[l] min(solve(nums, l2, r), solve(nums, l1, r-1)); // 取右端nums[r] 对手最优后剩下的最坏情况 int take_right nums[r] min(solve(nums, l, r-2), solve(nums, l1, r-1)); return max(take_left, take_right); }为什么取左端后要在solve(l2, r)与solve(l1, r-1)中取min因为对手下一步同样聪明他要么取新的左端l1剩下l2..r要么取右端r剩下l1..r-1他会选择让自己收益最大、也就是让你后续收益最小的分支。max(取左, 取右)与min(对手两种回应)层层交替正是 Minimax 的递归展开。最终判定Predict the Winner.cppint total accumulate(begin(nums), end(nums), 0); int player1 solve(nums, 0, n-1); int player2 total - player1; return player1 player2; // 玩家 1 不输即可3.2 建模二直接维护「分差」更优雅Predict the Winner.cpp 的 Approach-2 换了一个状态定义maxDiff(l, r)表示「当前玩家在区间[l, r]上能获得的最大净胜分自己 − 对手」。int maxDiff(vectorint nums, int l, int r) { if(l r) return nums[l]; if(t[l][r] ! -1) return t[l][r]; int take_left nums[l] - maxDiff(nums, l1, r); // 我拿 nums[l]之后轮到对方他也会最大化他自己的净胜分 int take_right nums[r] - maxDiff(nums, l, r-1); return t[l][r] max(take_left, take_right); } bool PredictTheWinner(vectorint nums) { return maxDiff(nums, 0, n-1) 0; }妙处在于递归中的符号自动完成了攻守互换——nums[l] - maxDiff(...)里的减号等价于「我的收益减去对方从剩余局面中能拿到的净胜分」。这种写法省去了求总和的步骤也是 Stone Game III.cpp 等题目反复使用的手法详见下文。Stone Game.cpp 的 Approach-2 还给出了一个有趣的数学结论当堆数为偶数且总数时先手 Alice 必赢直接return true复杂度 O(1)。3.3 自底向上按区间长度递推Optimal Strategy For A Game 中给出了 Top-Down自底向上版本按gap区间长度从 0 递增填充t[i][j]for(int gap 0; gap n; gap) { for(int i 0, j gap; j n; i, j) { if(gap 0) t[i][j] arr[i]; else if(gap 1) t[i][j] max(arr[i], arr[j]); else { int pick_left arr[i] min(t[i2][j], t[i1][j-1]); int pick_right arr[j] min(t[i1][j-1], t[i][j-2]); t[i][j] max(pick_left, pick_right); } } } return t[0][n-1];两种写法复杂度一致T.C : O(n^2)S.C : O(n^2)递归 记忆化更易写对自底向上则规避了递归栈开销适合面试中追问优化时展示。四、变体一一次可取多堆Stone Game II / III基础版每次只能取 1 堆扩展后每次可取1~K堆状态从二维升维但建模思路不变。4.1 Stone Game IILeetCode 1140状态携带 M题目规则当前玩家可取1..2M堆取完后M max(M, x)更新给对手。于是状态必须记录(person, i, M)三个维度Stone Game II.cpp 的实现int t[2][101][101]; // t[person][i][M] int solveForAlice(vectorint piles, int person, int i, int M) { if(i n) return 0; if(t[person][i][M] ! -1) return t[person][i][M]; int result (person 1) ? -1 : INT_MAX; int stones 0; for(int x 1; x min(2*M, n-i); x) { stones piles[ix-1]; if(person 1) { // Alice 回合最大化 result max(result, stones solveForAlice(piles, 0, ix, max(M, x))); } else { // Bob 回合最小化 Alice 的最终收益 result min(result, solveForAlice(piles, 1, ix, max(M, x))); } } return t[person][i][M] result; }要点用person维度区分当前行动者person 1时累计的是「Alice 的总分」因此 Bob 回合直接取min不对 stones 做累加——这是「目标函数固定在 Alice 总分」的写法枚举量x ∈ [1, min(2*M, n-i)]转移后M更新为max(M, x)复杂度T.C : O(n^3)状态数2·n·n每个状态枚举 O(n) 次取法、S.C : O(n^3)源码注释中标明该题是 META 高频题。4.2 Stone Game IIILeetCode 1406线性分差 DP此题每次可取 1~3 堆且允许取负值Alice 可能被迫得分减少因此目标改为最大化「Alice − Bob 的分差」。仓库给出四种递进写法Stone Game III.cpp递归 记忆化Approach-1核心就三行t[i] stoneValue[i] - solve(stoneValue, i1); // 取 1 堆 if(i1 n) t[i] max(t[i], stoneValue[i] stoneValue[i1] - solve(stoneValue, i2)); // 取 2 堆 if(i2 n) t[i] max(t[i], stoneValue[i] stoneValue[i1] stoneValue[i2] - solve(stoneValue, i3)); // 取 3 堆t[i]的定义是「从 i 开始当前玩家能获得的最大净胜分」- solve(ix)完成攻守互换与 Predict the Winner 的分差建模完全同构。最终diff solve(0)diff 0 → Alicediff 0 → Bob否则Tie。Approach-2 将其转为自底向上t[i] max(...)循环 i 从 n-1 到 0Approach-3 进一步压缩成 O(1) 空间只保留a t[i1]、b t[i2]、c t[i3]三个滚动变量Approach-4 则回到 Stone Game II 的显式 MiniMax 写法用player区分回合、Bob 回合对 stones 取负累计。同一道题四种写法覆盖了「递归 → 递推 → 滚动数组 → MiniMax 显式化」的完整优化路径非常值得对照阅读。五、变体二区间内切分Stone Game V / VII / VIII这一组不再是「取两端」而是「在区间内切一刀选择一半继续」前缀和成为标配工具。5.1 Stone Game VLeetCode 1563按左右和大小决定保留哪边规则在[l, r]内任选分界点mid分成[l, mid]与[mid1, r]两半分数 较小一半的和并继续在该半上递归和相等时可任选一边。Stone Game V.cpp 的递归 记忆化版本int solve(int l, int r, vectorint cumSum) { if(l r) return 0; // 不可再分 if(t[l][r] ! -1) return t[l][r]; int score 0; for(int mid l; mid r-1; mid) { int leftSum cumSum[mid] - (l-1 0 ? cumSum[l-1] : 0); // [l..mid] int rightSum cumSum[r] - cumSum[mid]; // [mid1..r] if(leftSum rightSum) score max(score, leftSum solve(l, mid, cumSum)); // 保留左半 else if(leftSum rightSum) score max(score, rightSum solve(mid1, r, cumSum)); // 保留右半 else score max({score, leftSum solve(l, mid, cumSum), rightSum solve(mid1, r, cumSum)}); // 任选一边 } return t[l][r] score; }前缀和cumSum让任意子段和以 O(1) 求取枚举分界点使复杂度来到T.C : O(n^3)、S.C : O(n^2)。Approach-2 给出等价的t[l][r]自底向上实现源码注释特别提醒Python 在该题会 TLE131/132 用例超时面试中应优先给出 C/Java 版本。5.2 Stone Game VIILeetCode 1690得分 剩余总和规则每次移除两端之一本回合得分 移除后剩余所有石头之和最后比总分。这个「得分依赖剩余和」的设定让转移变得特别Stone Game VII.cpp 中solve(l, r, sum)表示当前玩家在剩余和为 sum 的区间上能获得的最大净胜分int leftPick solve(stones, l1, r, sum-stones[l], t); int rightPick solve(stones, l, r-1, sum-stones[r], t); // 我拿左端 - 我得 (sum-stones[l])对手从剩余区间拿 leftPick 分净胜 return t[l][r] max(sum-stones[l]-leftPick, sum-stones[r]-rightPick);注意这里的sum是一个随递归变化的参数而非固定前缀和源码头部的手写推演A 13 - ...展示了如何从「按顺序写出双方得分」推导出「sum - stones[x] - 递归结果」的递推式适合用来练习「先手写小样例、再归纳状态转移」的解题流程。5.3 Stone Game VIIILeetCode 1872前缀和 线性 DP规则升级把前若干堆合并成新的第一堆得分 新前缀和然后对手继续。仓库给出递归 记忆化与自底向上两种解法Stone Game VIII.cppint solve(int i, vectorint prefixSum) { if(i n-1) return prefixSum[n-1]; // 只剩一个合并结果 if(t[i] ! -1) return t[i]; int take prefixSum[i] - solve(i1, prefixSum); // 本轮合并 0..i得分 prefixSum[i]之后轮到对手 int skip solve(i1, prefixSum); // 本轮不合并交给下一位 return t[i] max(take, skip); } return solve(1, prefixSum); // Alice 先手至少合并一堆从 i1 开始由于「得分 前缀和」子段和查询退化为 O(1)整题复杂度是线性的T.C : O(n)、S.C : O(n)。源码注释提示递归写法在 79/80 用例后 TLE底向上才是稳妥提交版——这是一个很好的「记忆化有时不够必须转递推」的现实案例。六、变体三取模计数Stone Game IXLeetCode 2029Stone Game IX 完全跳出了区间 DP 框架轮流取石头当前累计和模 3 等于 0 则轮到的一方立即输Alice 先手。仓库解法Stone Game IX.cpp只做三件事按stone % 3统计三类石头数量c0/c1/c2c0为偶数时(c1 1 c2 1)且差值条件→ Alice 赢c0为奇数时abs(c1 - c2) 3→ Alice 赢。if(c0 % 2 0) { // even return (c1 1 c2 1) (c2 c1 || c1 c2); } return abs(c1 - c2) 3;T.C : O(n)、S.C : O(1)。这类「看似博弈、实则数论计数」的题目在面试中常作为思维转折点出现——先判断是否真有状态转移再决定用 DP 还是数学结论避免对每个题都无脑套区间模板。七、变体四棋盘 状态压缩Maximum Number of Moves to Kill All PawnsLeetCode 3283最硬核的一题将博弈与「TSP 式 bitmask DP」结合Maximum Number of Moves to Kill All Pawns.cpp预处理从国王与每个兵的位置出发跑一次 BFS8 方向骑士步得到任意两关键点之间的最短步数minDist棋盘固定 50×50故 BFS 视为 O(1)博弈 DPdp[idx][mask]表示「当前在马位置 idx、还需消灭 mask 中剩余兵」时Alice 能领先的最大步数Alice 回合max、Bob 回合min与 Stone Game II 的person维度写法如出一辙复杂度T.C : O(n·2^n)n ≤ 15 左右状态n*2^nS.C : O(n*2^n)。该题的价值在于演示了「博弈 DP 状态如何扩展出第二个维度mask」——当可选动作是一个集合而非连续区间时bitmask 就是自然的局面编码。八、复杂度速查与刷题路线把本专题所有实现汇总成表便于面试前快速回忆题目状态定义转移核心时间复杂度空间复杂度Optimal Strategy For A Game / Predict the Winner / Stone Game(l, r)取两端 min/maxO(n²)O(n²)Stone Game II(person, i, M)取 1..2M 堆O(n³)O(n³)Stone Game III(i)一维分差取 1~3 堆O(n)O(1)~O(n)Stone Game V(l, r)区间切分 前缀和O(n³)O(n²)Stone Game VII(l, r, sum)移除端 剩余和O(n²)O(n²)Stone Game VIII(i)合并 前缀和O(n)O(n)Stone Game IX计数统计模 3 数学结论O(n)O(1)Maximum Number of Moves to Kill All Pawns(idx, mask)BFS 距离 bitmask 博弈O(n·2ⁿ)O(n·2ⁿ)推荐的按难度递进的练习顺序与仓库目录顺序一致入门模板Predict the Winner → Optimal Strategy For A Game → Stone Game掌握两种建模 数学结论扩展取法Stone Game III四种写法逐一吃透→ Stone Game II升维状态区间切分Stone Game V → Stone Game VII → Stone Game VIII体会从二维降到一维的优化跳出框架Stone Game IX数学计数与 Maximum Number of Moves to Kill All Pawnsbitmask 博弈作为压轴。九、小结DP/Game Strategy专题的价值不在于「会做 Stone Game 这一题」而在于它用 10 个实现把对抗性 DP 的完整知识图谱铺开了统一心法max自己回合与min对手回合交替或用分差建模让符号自动攻守互换状态设计三问局面用什么表示区间(l,r)位置i追加person/M/mask、动作集合是什么取两端 / 取 k 堆 / 切区间、子问题边界在哪优化三板斧前缀和Stone Game V/VIII、滚动数组Stone Game III、数学结论Stone Game / Stone Game IX。对照仓库源码逐题精读、亲手把递归改写成递推是掌握这一专题最高效的路径。每一份源码头部都标注了题号与公司标签如 Google、Adobe、Amazon、Microsoft、META可作为按公司备考的检索索引使用。【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考