总结一个玩家在两人游戏中可以拥有的所有可能值

问题描述

这是一款经典游戏，其中有两名玩家在以下游戏中玩:

This is a classical game where two players play following game:

连续有n个面额不同的硬币.在此游戏中，玩家从最左端或最右端挑选一个硬币(他们盲目地从任何一个极端中挑选概率为.5的硬币，两者都是愚蠢的).我只想计算开始游戏的玩家的预期总和.

There are n coins in a row with different denominations. In this game, players pick a coin from extreme left or extreme right (they blindly pick from any extreme with a probability of .5, both of them are dumb). I just want to count the expected sum of player who starts the game.

为此，我想总结一个球员可以拥有的所有可能的价值组合.我正在使用一个递归解决方案，该解决方案总结所有可能的结果值，但是它具有重叠的子问题.我想提高效率，并要记住这些重叠的子问题.

For this I want to sum up all the possible combinations of values a player can have. I am using a recursive solution which sums up all the possible outcome values but it is having overlapping sub-problems. I want to make it efficient and want to memoize these overlapping sub-problems.

我无法收集执行它的逻辑.请有人帮忙.

I am not able to collect the logic to execute it. Please someone help.

推荐答案

想法适用于每行子间隔，以存储两个玩家的总和.

Idea is for each row subinterval to store sums for both players.

让F(start, end)表示间隔[start, end]上的第一个玩家的可能总和.类似的定义S(start, end).我们可以用字典将和的概率存储为可能的和，例如{2: 0.25, 5: 0.25, 6: 0.5}.

Let F(start, end) denote possible sums of first player playing on interval [start, end]. Similar define S(start, end). We can store possible sums with a probabilities of sums with a dictionary, like {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

这可以通过增加间隔长度来计算:

This can be calculated by increasing interval length:

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)用于计算预期总和.

Dictionaries F(1, row_length) and S(1, row_length) are used to calculate expected sum.

这篇关于总结一个玩家在两人游戏中可以拥有的所有可能值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！