如何设计递归算法预测双方最优策略下的取数游戏结果

问题规则 #

• 游戏输入为存储数字序列的数组，玩家每回合仅允许从数组的**两端（头部或尾部）**选取一个数字
• 选中的数字直接累加至当前玩家的总得分，选数完成后立即轮换对方玩家行动，对方同样只能从剩余数组的两端选数
• 数组内所有数字被取完后，对比双方总得分，分数更高的一方获胜
• 要求实现递归算法，覆盖所有可能的选择组合，最终返回双方均采取最优策略时，先手玩家的最终得分。

当初始数组长度为4时，所有可能的游戏推演路径可通过二叉树结构完整可视化，每个节点代表当前剩余的数组状态，两个子分支分别对应当前玩家选头部、选尾部的决策，叶子节点对应游戏终局。

核心递归逻辑 #

不用搞复杂的状态记录，抓住一个核心就行：当前玩家做出任意选择后，剩余子数组的对局中，对方玩家也会采取完全相同的最优策略，最大化他自己的净收益。

我们定义递归函数opt_diff(i,j)的返回值为：当前玩家面对从索引i到j的剩余子数组时，能拿到的比对方玩家多的最大净分差。递归推导规则如下：

1. 终止条件：当i == j时，子数组只剩一个数字，当前玩家直接取走，返回nums[i]即可
2. 如果当前玩家选头部的nums[i]，那么剩下的i+1到j子数组中，对方玩家成为先手，能拿到的净分差为opt_diff(i+1,j)，折算到当前玩家的净收益就是nums[i] - opt_diff(i+1,j)
3. 如果当前玩家选尾部的nums[j]，同理可得当前玩家净收益为nums[j] - opt_diff(i,j-1)
4. 当前玩家会选择两个选项中净收益更高的走法，因此返回两个值的较大值即可

拿到全局的净分差后，结合数组总和就能算出先手玩家的最终得分：设先手总分为s1，后手为s2，那么s1 + s2 = sum(nums)，s1 - s2 = opt_diff(0, len(nums)-1)，解二元一次方程可得s1 = (sum(nums) + 全局净分差) // 2。

基础递归代码实现（Python） #

def get_optimal_first_score(nums):
    def cal_max_diff(i, j):
        # 只剩一个数，当前玩家直接取
        if i == j:
            return nums[i]
        # 分别计算选头、选尾的净收益
        pick_head = nums[i] - cal_max_diff(i+1, j)
        pick_tail = nums[j] - cal_max_diff(i, j-1)
        # 选收益更高的选项
        return max(pick_head, pick_tail)
    total_sum = sum(nums)
    max_diff = cal_max_diff(0, len(nums)-1)
    return (total_sum + max_diff) // 2

提示：上面的基础递归写法会重复计算已经算过的子数组状态，如果输入数组长度比较大，可以加个缓存存已经算过的(i,j)对应的分差，能把时间复杂度从O(2^n)降到O(n²)，核心的递归逻辑不用改。

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