企业官网建设流程全解析

1. 石子游戏 III 问题解析

1406. Stone Game III 是 LeetCode 上一道经典的动态规划博弈问题。题目描述如下：Alice 和 Bob 轮流从一排石堆中取石子，每次可以从当前石堆开始取走 1、2 或 3 堆石子。游戏结束时，拥有更多石子的玩家获胜。假设双方都采取最优策略，我们需要判断 Alice 是否能获胜，或者游戏是否会以平局告终。

1.1 问题核心特征

这道题具有几个关键特征：

1. 轮流决策：玩家交替进行选择
2. 有限选择：每次只能取 1-3 堆石子
3. 完全信息：所有石堆信息对双方公开
4. 最优策略：双方都会采取对自己最有利的选择

这类博弈问题的关键在于：当前玩家的最优选择取决于后续玩家的可能选择。这正是动态规划能够完美解决的问题场景。

2. 动态规划解法详解

2.1 状态定义

我们定义 dp[i] 表示：当游戏进行到第 i 堆石子时，当前玩家能比对手多获得的最大石子数。这里的"当前玩家"指的是此时轮到的玩家，可能是 Alice 或 Bob。

例如：

• dp[i] = 5 表示从第 i 堆开始，当前玩家可以比对手多拿 5 个石子
• dp[i] = -3 表示对手可以比当前玩家多拿 3 个石子

2.2 状态转移方程

对于每个位置 i，当前玩家有三种选择：

1. 取 piles[i]：获得 piles[i]，对手从 i+1 开始，能比当前玩家多拿 dp[i+1]
   • 净收益：piles[i] - dp[i+1]
2. 取 piles[i]+piles[i+1]：对手从 i+2 开始
   • 净收益：(piles[i]+piles[i+1]) - dp[i+2]
3. 取 piles[i]+piles[i+1]+piles[i+2]：对手从 i+3 开始
   • 净收益：(piles[i]+piles[i+1]+piles[i+2]) - dp[i+3]

因此状态转移方程为： dp[i] = max( piles[i] - dp[i+1], piles[i] + piles[i+1] - dp[i+2], piles[i] + piles[i+1] + piles[i+2] - dp[i+3] )

2.3 边界条件

当剩余石子不足 3 堆时：

• 如果 i == n（没有石子可取）：dp[i] = 0
• 如果 i == n-1：只能取 piles[n-1]
• 如果 i == n-2：可以取 piles[n-2] 或 piles[n-2]+piles[n-1]

2.4 实现代码

def stoneGameIII(piles): n = len(piles) dp = [0] * (n + 3) # 多预留3位避免边界检查 for i in range(n-1, -1, -1): dp[i] = -float('inf') take = 0 for k in range(3): if i + k >= n: break take += piles[i + k] dp[i] = max(dp[i], take - dp[i + k + 1]) if dp[0] > 0: return "Alice" elif dp[0] < 0: return "Bob" else: return "Tie"

3. 算法优化与细节

3.1 空间优化

上述实现使用了 O(n) 的空间。观察状态转移方程可以发现，dp[i] 只依赖于 dp[i+1] 到 dp[i+3]，因此可以将空间优化到 O(1)：

def stoneGameIII(piles): n = len(piles) dp1, dp2, dp3 = 0, 0, 0 for i in range(n-1, -1, -1): current = -float('inf') take = 0 for k in range(3): if i + k >= n: break take += piles[i + k] current = max(current, take - [dp1, dp2, dp3][k]) dp3, dp2, dp1 = dp2, dp1, current if dp1 > 0: return "Alice" elif dp1 < 0: return "Bob" else: return "Tie"

3.2 时间复杂度分析

该算法有两层循环：

• 外层循环：遍历所有石子堆，O(n)
• 内层循环：最多3次选择，O(1) 因此总时间复杂度为 O(n)，空间复杂度优化后为 O(1)。

4. 常见错误与调试技巧

4.1 边界条件处理

常见错误包括：

1. 数组越界：当 i+k >= n 时没有及时终止
2. 初始化不当：dp数组初始值应设为负无穷（表示极小值）
3. 结果判断错误：dp[0]>0 表示Alice赢，而不是dp[0]最大

调试技巧：

• 打印dp数组中间值
• 用小规模测试用例手动验证（如[1,2,3]）

4.2 记忆化搜索实现

除了迭代法，也可以用记忆化搜索实现：

def stoneGameIII(piles): n = len(piles) from functools import lru_cache @lru_cache(maxsize=None) def dfs(i): if i >= n: return 0 res = -float('inf') take = 0 for k in range(3): if i + k >= n: break take += piles[i + k] res = max(res, take - dfs(i + k + 1)) return res score = dfs(0) if score > 0: return "Alice" elif score < 0: return "Bob" else: return "Tie"

5. 博弈问题通用解法

这类博弈问题有通用解法模式：

1. 定义状态：通常表示当前局面下的最优结果
2. 状态转移：考虑所有可能的移动，选择最优解
3. 边界条件：游戏结束时的基准情况
4. 结果判断：根据初始状态的值决定胜负

类似题目包括：

• 486. Predict the Winner
• 877. Stone Game
• 1140. Stone Game II

关键思路都是：当前玩家的收益 = 本次选择获得的收益 - 对手后续的最优收益。这种"我选-你选"的交替模式是博弈DP的核心。