双人最优策略硬币收集游戏先手最大可获价值求解问询

解法思路 #

这是典型的零和博弈动态规划问题，我们可以通过以下思路推导： #

1. 前置预处理 #

先计算硬币的前缀和数组pre_sum，其中pre_sum[i]表示前i枚硬币的总价值，pre_sum[0] = 0，pre_sum[k] = arr[0] + arr[1] + ... + arr[k-1]，可以在O(n)时间内完成，方便后续快速计算任意区间的硬币和。 #

2. 状态定义 #

定义dp[i][s]为：当前剩余硬币从数组第i位开始（前i位已经被取完），当前取币上限参数为s时，当前行动玩家能拿到的最大硬币总价值。
我们要求的最终结果就是初始状态dp[0][1]（初始没有硬币被取走，S=1，当前行动玩家是先手player1）。 #

3. 状态转移 #

零和博弈下有一个核心特性：当前玩家的最大收益 = 剩余所有硬币的总价值 - 下一个玩家在后续状态的最大收益。
对当前状态(i,s)，当前玩家可取的硬币数量k满足1 ≤ k ≤ min(2*s, n-i)（不能超过上限，也不能超过剩余硬币数），对每一个合法的k：

• 当前玩家取走前k枚硬币，获得价值pre_sum[i+k] - pre_sum[i]
• 接下来的状态变为：剩余硬币从i+k位开始，新的S更新为max(s, k)，下一个玩家在这个新状态下的最大收益是dp[i+k][max(s,k)]
• 因此当前玩家选k时的总收益为(pre_sum[n] - pre_sum[i]) - dp[i+k][max(s, k)]，其中pre_sum[n] - pre_sum[i]是当前剩余所有硬币的总价值
  我们只需要遍历所有合法的k，取收益最大值即可：
  dp[i][s] = max( (pre_sum[n] - pre_sum[i]) - dp[i+k][max(s, k)] ) ，k∈[1, min(2s, n-i)]

4. 边界条件 #

当i ≥ n时，没有剩余硬币，当前玩家收益为0，即对任意s，dp[i][s] = 0。 #

5. 实现方式与复杂度 #

可以用记忆化递归或者从后往前的递推实现，总状态数为O(n²)，每个状态的转移最多遍历O(n)个k，整体时间复杂度为O(n²)，对于n≤1000的场景完全可以跑通。 #

示例验证 #

对输入[3,6,8,5,4]，pre_sum = [0,3,9,17,22,26]：

• 初始状态dp[0][1]可选k=1或k=2
  • 选k=1时，后续状态为dp[1][1]，计算得dp[1][1]的最大值为14（player2的最优收益），因此当前玩家收益为26 - 14 = 12
  • 选k=2时，后续状态为dp[2][2]，计算得player2的最优收益为17，当前玩家收益为26 - 17 =9
• 取最大值12，和示例结果一致。

内容的提问来源于stack exchange，提问作者daniel