了解寻找最佳策略的解决方案,包括挑选金罐

Question

我无法理解CareerCup上这个问题的解决方案背后的原因.

黄金游戏:两个玩家A和B.有一排金币排成一行,每个包含一些金币(玩家可以看到每个金罐中有多少硬币 - 完美的信息).他们得到交替转弯,玩家可以从线的一端挑选一个底池.获胜者是最终拥有更多硬币的玩家.目标是"最大化"A收集的硬币数量,假设B也是最佳的.A开始游戏.

我们的想法是找到一个最佳策略,让A赢知道B也是最优秀的.你会怎么做？

最后我被要求编写这个策略!

这是谷歌采访中的一个问题.

建议的解决方案是:

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]？它总是留下一个硬币罐.不应该是[开始+ 1,结束]因为我们把起始硬币罐拿出来了吗？
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.他发挥最大化他的收益.然而,由于硬币的数量是固定的,这相当于最小化了我的.注意

• 如果他出场,start+1我会获益max_coin(coin, start+2, end)
• 如果他玩得end不好max_coin(coin, start+1, end-1)

由于他试图最小化我的收益,我将获得这两者中的最小值.

同样的推理也适用于我玩的其他线路end.

注意:这是一个糟糕的递归实现.首先max_coin(coin, start+1, end-1)计算两次.即使你解决了这个问题,你最终也会计算出大量的时间.这与您尝试使用递归计算Fibonacci数时会发生的情况非常相似.使用memoization或动态编程会更好.

Answer 2

a并且b这里分别表示A通过选择起始底池或结束底池可以获得的最大值.

我们实际上试图最大化A-B,但是从那时起B = TotalGold - A,我们试图最大化2A - TotalGold,并且由于TotalGold是不变的,我们试图最大化2A,这是相同的A,所以我们完全忽略了选择的价值B并且只是合作A.

递归调用中更新的参数也包括B拾取 - 所以coin[start]表示A选择开始,然后B从开始选择下一个,所以它是start+2.对于下一个电话,B从最后选择,所以它start+1和end-1.其余部分也是如此.

我们正在考虑min,因为它B会尽量使自己的利润最大化,因此它会选择最小化A利润的选择.

但实际上我会说这个解决方案缺乏一点意义,它只返回一个值,而不是"最优策略",在我看来,这将是一系列动作.并且它也没有考虑到A无法获胜的可能性,在这种情况下,人们可能想要输出一条消息,表明这是不可能的,但这实际上是与面试官澄清的事情.