动态规划解决两端划数博弈问题的策略咨询

问题概述 #

给定长度为偶数N（2≤N≤100）的正整数序列，每个数不超过200。两名玩家轮流从序列两端取一个数字加入自己得分，先手先行动。需计算先手在对手采用最优策略时能获得的最大得分。

动态规划核心思路 #

1. 状态定义 #

定义dp[i][j]为当子序列为第i到第j个元素（下标从0开始）时，当前玩家能获得的与对手的得分差的最大值。这个定义的核心是把博弈转化为得分差的最优选择——对手会采取对自己最有利的策略，也就是最小化当前玩家的得分差。

2. 状态转移方程 #

当前玩家有两种选择：

• 取左端元素a[i]：此时剩下的子序列是i+1到j，轮到对手行动，对手会拿到该子序列的最优得分差，因此当前玩家的总得分差为a[i] - dp[i+1][j]（对手的得分差是其相对于当前玩家的优势，所以要减去）。
• 取右端元素a[j]：同理，当前玩家的总得分差为a[j] - dp[i][j-1]。

状态转移方程为：

dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])

3. 初始条件 #

当子序列只有一个元素（i == j）时，当前玩家只能取这个元素，得分差就是该元素的值：

dp[i][i] = a[i]

4. 计算先手最终得分 #

设序列所有元素的总和为total_sum，先手得分first_score，后手得分second_score，则：

• first_score - second_score = dp[0][N-1]
• first_score + second_score = total_sum

联立解得：

first_score = (total_sum + dp[0][N-1]) // 2

示例验证 #

以示例输入序列[4,7,2,9,5,2]为例：

• 总和total_sum = 4+7+2+9+5+2 = 29
• 计算得dp[0][5] = 7
• 先手得分(29+7)//2 = 18，与示例输出一致。

实现步骤提示 #

• 读取输入，将序列存入数组a。
• 初始化一个N×N的二维数组dp，填充初始条件。
• 按子序列长度从小到大计算dp[i][j]（长序列的结果依赖短序列的计算）：从长度2开始，到长度N结束。
• 最后通过总和和dp[0][N-1]计算先手得分。

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