这是一个经典游戏,两个玩家玩以下游戏:
一排有 n 种不同面额的硬币。在这个游戏中,玩家从极左或极右挑选硬币(他们盲目地从概率为 0.5 的任何极端中挑选,他们都是哑巴)。我只想计算开始游戏的玩家的预期总和。
为此,我想总结一下玩家可以拥有的所有可能的价值组合。我正在使用一个递归解决方案,它总结了所有可能的结果值,但它有重叠的子问题。我想让它变得高效,并想记住这些重叠的子问题。
我无法收集执行它的逻辑。请有人帮忙。
这是一个经典游戏,两个玩家玩以下游戏:
一排有 n 种不同面额的硬币。在这个游戏中,玩家从极左或极右挑选硬币(他们盲目地从概率为 0.5 的任何极端中挑选,他们都是哑巴)。我只想计算开始游戏的玩家的预期总和。
为此,我想总结一下玩家可以拥有的所有可能的价值组合。我正在使用一个递归解决方案,它总结了所有可能的结果值,但它有重叠的子问题。我想让它变得高效,并想记住这些重叠的子问题。
我无法收集执行它的逻辑。请有人帮忙。
想法是为每一行子间隔存储两个玩家的总和。
让F(start, end)
表示第一个玩家在 interval 玩的可能总和[start, end]
。类似的定义S(start, end)
。我们可以用字典存储可能的总和,比如{2: 0.25, 5: 0.25, 6: 0.5}
.
比递归成立:
F(start, end) = {row[end] +sum: p/2, for sum,p in S(start, end-1)} +
{row[start]+sum: p/2, for sum,p in S(start+1, end)}
S(start, end) = {sum: p/2, for sum,p in F(start, end-1)} +
{sum: p/2, for sum,p in F(start+1, end)}
F(start, end) = {row[start]: 1} if start == end
S(start, end) = {} if start == end
这可以通过增加间隔长度来计算:
for length = 0 to row_length-1:
for start = 1 to row_length - length:
calculate `F(start, start+length)` and `S(start, start+length)`
字典F(1, row_length)
和S(1, row_length)
用于计算预期总和。