algorithm - 了解为涉及采金 jar 的游戏寻找最佳策略的解决方案

Question

我无法理解 this question on CareerCup 解决方案背后的原因.

Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

这是 Google 面试中的一个问题。

建议的解决方案是:

function max_coin( int *coin, int start, int end ):
    if start > end:
        return 0

    // I DON'T UNDERSTAND THESE NEXT TWO LINES
    int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))
    int b = coin[end] + min(max_coin(coin, start+1,end-1), max_coin(coin, start, end-2))

    return max(a,b)

有两个具体部分我不明白:

1. 在第一行中，为什么我们使用范围 [start + 2, end] 和 [start + 1, end - 1]？它总是遗漏一个硬币 jar 。不应该是[start + 1, end]因为我们把起始币 jar 拿出来了吗？
2. 在第一行中，为什么我们取两个结果中的最小值而不是最大值？
3. 因为我对为什么这两行取最小值以及为什么我们选择这些特定范围感到困惑，所以我不太确定 a 和 b 实际代表什么？

Answer 1

首先a和b分别代表播放start(分别为end)时的最大增益.

让我们解释一下这一行:

int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))

如果我玩start，我会立即获得coin[start]。另一个玩家现在必须在 start+1 和 end 之间玩。他玩游戏是为了最大化他的 yield 。然而，由于硬币的数量是固定的，这相当于最小化我的。注意

• 如果他玩 start+1 我将获得 max_coin(coin, start+2, end)
• 如果他玩 end 我将获得 max_coin(coin, start+1, end-1)

因为他试图最小化我的 yield ，所以我将获得这两者中的最小值。

同样的推理适用于我播放 end 的另一行。

注意:这是一个糟糕的递归实现。首先，max_coin(coin, start+1, end-1) 被计算了两次。即使你解决了这个问题，你最终也会计算出很多时间更短的情况。这与您尝试使用递归计算斐波那契数列时发生的情况非常相似。最好使用记忆化或动态编程。