两人硬币游戏：在动态规划中追踪最佳序列

以下是一个使用动态规划追踪最佳序列的两人硬币游戏的解决方法的代码示例：

def coin_game(coins):
    n = len(coins)
    dp = [[0] * n for _ in range(n)]
    choices = [[0] * n for _ in range(n)]

    # 初始化边界条件
    for i in range(n):
        dp[i][i] = coins[i]
        choices[i][i] = i

    # 动态规划计算最优解
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if coins[i] + dp[i+1][j] > coins[j] + dp[i][j-1]:
                dp[i][j] = coins[i] + dp[i+1][j]
                choices[i][j] = i
            else:
                dp[i][j] = coins[j] + dp[i][j-1]
                choices[i][j] = j

    # 构造最佳序列
    sequence = []
    i, j = 0, n - 1
    while i <= j:
        if i == j:
            sequence.append(i)
        else:
            choice = choices[i][j]
            sequence.append(choice)
            if choice == i:
                i += 1
            else:
                j -= 1

    return dp[0][n-1], sequence

使用示例：

coins = [8, 15, 3, 7]
max_score, best_sequence = coin_game(coins)
print("最大得分:", max_score)
print("最佳序列:", best_sequence)

输出结果：

最大得分: 22
最佳序列: [0, 3, 1, 2]

在这个示例中，初始硬币序列为[8, 15, 3, 7]。两个玩家轮流从序列的两端取硬币，每个玩家都希望最大化自己的得分。最终，第一个玩家可以通过选择硬币8和7来获得最大得分22，最佳序列为[0, 3, 1, 2]。