algorithm - 最优选择算法

Question

我今天有一个大学的约会，我开始紧张起来。我们最近讨论了算法优化的动态规划，现在我们将实现一个使用动态规划的算法。
任务
因此，我们有一个简单的游戏，我们将编写一个算法，找出最佳可能的策略，以获得最佳可能的得分（假设两个玩家都玩优化）。
我们有一行类似于4 7 2 3的数字（注意，根据任务描述，它并不总是一个相等的数字计数）。现在每个玩家轮流从后面或前面取一个数字。当最后一个数字被选中时，每个玩家的数字被相加，每个玩家的分数被相互减除。结果就是1号选手的得分所以上述数字的最佳顺序是
P1:3->P2:4->P1:7->P2:2
所以p1会有3, 7而p2会有4, 2这将导致玩家1的最终得分(3 + 7) - (4 + 2) = 4。
在第一个任务中，我们应该简单地实现“一个简单的递归方法来解决这个问题”，在这里我只使用了一个minimax算法，这个算法对于自动化测试来说似乎很好。然而，在第二个任务中，我陷入了困境，因为我们现在将使用动态编程技术。我发现的唯一提示是在任务本身中提到了amatrix。
到目前为止我所知道的
我们有一个单词转换问题的例子，在使用这样的矩阵时，它被称为两个单词的Edit distance，这意味着将一个单词转换成另一个单词需要多少字母的变化（插入、删除、替换）这两个单词按表或矩阵排序，每个单词的组合计算距离。
例子：

W    H    A         T
     | D       | I
     v         v
W         A    N    T

编辑距离为2您有一个表，其中每个子字符串的每个编辑距离显示如下：

   ""    W    H    A    T
         1    2    3    4

   W 1   0    1    2    3

   A 2   1    1    2    3

   N 3   2    2    2    3

   T 4   3    3    3    2

例如从 WHA到 WAN需要两次编辑：insert n和delete h，从 WH到 WAN还需要两次编辑：substituce h->a和insert n等等。这些值是用“opt”函数计算的，我认为它代表优化。
我还学习了自下而上和自上而下的递归方案，但我不太确定如何将其附加到我的问题上。
我所想的
作为提醒，我使用数字 4 7 2 3。
我从上面学到，我应该尝试创建一个表，在其中显示每个可能的结果（就像minimax一样，它将被保存在前面）。然后，我创建了一个简单的表，其中我试图包括可能的绘图，可以这样做（我认为这是我的OPT函数）：

         4    7    2    3
       ------------------
a.  4 |  0   -3    2    1
      |
b.  7 |  3    0    5    4
      |
c.  2 | -2   -5    0   -1
      |
d.  3 | -1   -4    1    0

左栏标记玩家1绘制，上排标记玩家2绘制，每个数字代表 numberP1 - numberP2从这个表中，我至少可以读到上面提到的3->4->7->2（-1+5）的最优策略，所以我确定这个表应该包含所有可能的结果，但我现在不太确定如何从中得出结果。我的想法是开始遍历这些行，选择其中数字最高的一行，并将其标记为p1中的pick（但无论如何这都是贪婪的）。然后，p2将搜索这一行中的最低数字，并选择特定的条目，然后轮到它。
例子：
p1选择行a. 7 | 3 0 5 4，因为5是表中的最高值p2现在从那一行中选择3，因为它是最低的（0是无效的，因为它是同一个数字，你不能选择两次），所以第一个回合是7->4，但我注意到，这个抽签是不可能的，因为7从一开始就不可访问。因此，每转一圈，你只有4种可能：表的外部编号和直接在表后/表前的编号，因为这些编号在绘图后可以访问。所以第一个回合我只有A排或D排，从P1可以选择：
剩下的p2是7或3。或者p1取3，p2取4或2
但我真的不知道如何从中得出结论，我真的陷入了困境。
所以我真的很想知道我是不是在正确的道路上，或者我是否过度思考这个问题。这是解决这个问题的正确方法吗？

Answer 1

在开始动态编程算法时，首先应该尝试写下一个递归关系。
我们先把问题简单化一点。我们将考虑牌的数量是偶数，并且我们希望为第一个玩家设计一个最佳策略。一旦我们解决了这个版本的问题，其他的（奇数张牌，第二个玩家的优化策略）就很简单了。
所以，首先，一个递归关系。让X(i, j)成为玩家1所能期望的最佳分数（当玩家2也在最佳状态时），当剩余的牌从i^th到j^th时。然后，玩家1在玩游戏时期望的最佳分数将由X(1, n)表示。
我们有：
X(i, j) = max(Arr[i] + X(i+1, j), X(i, j-1) + Arr[j])如果j-i % 2 == 1，这意味着玩家可以期望的最佳分数是在左边拿牌和右边拿牌之间的最佳分数。
在另一种情况下，另一个玩家正在玩，所以他会尽量减少：
X(i, j) = min(Arr[i] + X(i+1, j), X(i, j-1) + Arr[j])如果j-i % 2 == 0。
终端案例很简单：X(i, i) = Arr[i]，这意味着当只有一张卡时，我们只需选择它，仅此而已。
现在算法没有动态规划，这里我们只把递归关系写成递归算法：

function get_value(Arr, i, j) {
    if i == j {
        return Arr[i]
    } else if j - i % 2 == 0 {
        return max(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    } else {
        return min(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    }
}

这个函数的问题是，对于某些给定的 i, j，会有许多冗余的 X(i, j)计算动态规划的本质是存储中间结果，以防止重复计算。
带有动态编程的algo（x初始化时处处 + inf。

function get_value(Arr, X, i, j) {
    if X[i][j] != +inf {
        return X[i][j]
    } else if i == j {
        result = Arr[i]
    } else if j - i % 2 == 0 {
        result = max(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    } else {
        result = min(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    }
    X[i][j] = result
    return result
}

正如您所看到的，与上述算法的唯一区别是，我们现在使用2d数组 X来存储中间结果。由于第一种算法在 O(2^n)中运行，而第二种算法在 O(n²)中运行，因此时间复杂性的结果是巨大的。