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

我无法理解this question on CareerCup解决方案背后的原因。了解寻找最佳策略的解决方案，包括挑选金壶

花盆黄金游戏：选手A & B.有黄金盆一条线布置，每个都包含了一些金币（玩家可以看到多的硬币是如何出现在每个第一桶金 - 完美信息）。他们得到交替轮次，其中玩家可以从线路的末端之一挑选一个锅。赢家是最后有更高号码的玩家。目标是“最大化”A收集的硬币的数量，假设B也发挥最佳效果。 A开始比赛。

这个想法是找到一个最佳策略，让A赢得知道 B也玩的最佳。你会怎么做？

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

这是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)

有两个具体的部分我不明白：

在第一行，为什么我们使用范围[开始+ 2，结束]和[开始+ 1，结束 - 1]？它总是抛出一个硬币罐。它不应该[开始+ 1，结束]，因为我们把开始的硬币罐拿出来了吗？
在第一行中，为什么我们取两个结果的最小值而不是最大值？
因为我对两条线为什么会最小以及为什么选择这些特定范围感到困惑，我不确定a和b究竟代表什么？

来源

2014-03-05 tina nyaa

你确定这是java吗？ –

你必须递归地解决每个子任务。 – sp1rs

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不可能赢的可能性，在这种情况下，人们可能希望输出一条消息，说这是不可能的，但这真的是要与面试官澄清的事情。

来源

2014-03-05 11:03:47 Dukeling

让我以相反的顺序回答你的观点，不知何故它似乎更有意义。

3 - a，b表示硬币的第一个球员将获得的金额，当他/她选择的第一或相应的最后一桶

2 - 我们取最小值，因为这是第二次的选择玩家 - 他/她将采取行动，尽量减少第一名玩家获得的硬币数量

1 - 第一行介绍场景 - 如果第一个玩家拿到第一个玩家，第二个玩家会做什么？如果他/她再次拿到第一个底池，它将离开（开始+ 2，结束）。如果他/她拿到最后一个罐子，它将离开（开始+1，结束-1）

来源

2014-03-05 11:03:24

首先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)。即使你解决了这个问题，你也会在很短的时间内完成计算。这与如果您尝试使用递归计算斐波纳契数字的情况非常相似。使用记忆或动态编程会更好。

来源

2014-03-05 11:05:13 hivert

你能解释一下如何用动态规划解决上述问题。 –

@coder_15您只需将中间值存储在表中或类似的地方以避免重新计算它们。 –

加1以获得更好的解释 – Humoyun

假设你在你的回合中获得的是x并且你在所有轮流中得到的结果是y。这两个值代表x+y，其中a假设您从前面拿下一个底池（x=coin[start]），b假定您从后面拿下您的下一个底池（x=coin[end]）。

现在你如何计算y。

经过您的选择后，对手将使用相同的最佳策略（因此递归调用）来最大化他的利润，并且您将在本回合中获得较少的利润。这就是为什么你的y=min(best_strategy_front(), best_strategy_end()) - 你的价值是剩下的两个选择中较小的一个，因为对手会选择更大。

索引只是表示您做出选择后，其余序列在正面和背面减去一个底部。

来源

2014-03-05 11:08:23

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

回答

相关问题