最大化2个玩家所选数字之和的差异

Question

我有2个问题来自一个简单的问题。我将用我找到的解决方案解释简单的问题，然后解决修改后的问题。

假设有一个游戏有2个玩家，A和B以及正整数列表。玩家A首先从列表中取出一个数字，玩家B做同样的事情，依此类推，列表中不再有数字。两位玩家总结了所选数字。每个玩家的目标是最大化他的总和与对手的总和之间的差异，即总分。问题是如果两个玩家以最佳方式玩，玩家A可以获得的最高分数是多少。

现在，为此，我发现每个玩家的最佳策略是在每一步采取最大数量，伪代码如下：

sumA = 0
sumB = 0
list = [1, 5, 3, 7, 9]

while list IS NOT EMPTY:
    val = pop_max(list)
    sumA = sumA + val

    if list IS NOT EMPTY:
        val = pop_max(list)
        sumB = sumB + val


scoreA = sumA - sumB
print scoreA

这可以在O（n）或O（n * log（n））中运行，具体取决于列表中的数字是如何排序的。

以下2个修改：

在游戏玩家A的开头应该从列表中删除K个数字。如果他以最佳方式做到这一点，之后游戏是最初的，他可以获得的格言得分是多少？

和

在每一步中，玩家可以从列表中选择最左边或最右边的数字。他们再次以最佳方式进行游戏。玩家A可以获得的最高分数是多少？

对于第二个修改，我可以想到一个强力方法，即计算所有可能性的树，但这对大输入数据不起作用。我相信有一种DP算法。

对于第一次修改，我想不到一个想法。

有人可以为这两个修改提供一些算法思路吗？

[LATTER EDIT]

第二次修改的解决方案可以在这里找到https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/它是DP。

Answer 1

这是第二次修改的帖子，即

在每一步中，玩家可以从列表中选择最左边或最右边的数字。他们再次以最佳方式进行游戏。玩家A可以获得的最高分数是多少？

解决方案基于DP。对于子问题（i-n），即qazxsw poi，有两种选择：

1. 用户选择值为v [i]的第i个元素：对手选择第（i + 1）个元素或第j个元素。对手打算选择离开用户最小值的元素。即用户可以收集值v[]i, v[i+1], ..., v[j]

v[i] + min(F(i+2, j), F(i+1, j-1))

2. 用户选择值为v [j]的第j个元素：对手选择第i个元素或第（j-1）个元素。对手打算选择离开用户最小值的元素。即用户可以收集值

v[j] + min(F(i+1, j-1), F(i, j-2))

以下是基于以上两种选择的递归解决方案。我们最多选择两个选项。

F（i，j）表示用户可以从第i个硬币到第j个硬币收集的最大值。

F（i，j）= Max（v + i）+ min（F（i + 2，j），F（i + 1，j-1），v [j] + min（F（i + 1， j-1），F（i，j-2）））

基础案例

F（i，j）= v [i]如果j == i

F（i，j）= max（v [i]，v [j]）如果j == i + 1

这是Python中的一段代码，可以解决它

[消息来源]

def optimalStrategyOfGame(arr, n): 

    # Create a table to store solutions of subproblems  
    table = [[0 for i in range(n)] for i in range(n)] 

    # Fill table using above recursive formula. Note that the table is  
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.  
    for gap in range(n): 
        for j in range(gap, n): 
            i = j - gap 

            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is  
            # F(i, j-2) in above recursive formula  
            x = 0
            if((i + 2) <= j): 
                x = table[i + 2][j] 
            y = 0
            if((i + 1) <= (j - 1)): 
                y = table[i + 1][j - 1] 
            z = 0
            if(i <= (j - 2)): 
                z = table[i][j - 2] 
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z)) 
    return table[0][n - 1]