algorithm - 钉子游戏 : best place to place ball such that it lands in the target cell

Question

来源:Facebook Hacker Cup Qualification Round 2011

在 Playground ，您可以玩一个简单的游戏，将一个球从您选择的位置扔到游戏的顶部。球在游戏中掉落时会弹开许多钉子。每当球碰到钉子时，它会以 0.5 的概率向左弹跳，以 0.5 的概率向右弹跳。唯一的异常(exception)是当它撞到最左侧或最右侧的钉子时，在这种情况下它总是向中间反弹。

最初制作游戏时，钉子排列成规则的网格。然而，这是一款老游戏，现在有些钉子不见了。您在游戏中的目标是让球在特定位置掉出游戏底部。在给定比赛安排的情况下，我们如何才能确定最佳的落球位置，从而使球落到这个特定位置的概率最大？

下图显示了一个包含五行五列的游戏示例。请注意，顶行有五个钉子，下一行有四个钉子，接下来的五个，依此类推。有五列，有四种选择可以将球放入(从 0 开始索引)。请注意，在此示例中，缺少三个钉子。顶行是第 0 行，最左边的钉子是第 0 列，所以缺失的钉子的坐标是 (1,1)、(2,1) 和 (3,2)。在这个例子中，最好的落球位置是最左边的第 0 列，这给出了 50% 的机会它会落入球门。

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x
 G

x 表示钉子，。 表示空白。

Answer 1

从底部开始，将概率 1 分配给目标，将 0 分配给其他位置。然后对于下一行，按如下方式分配概率:

1) if there is no peg, use the probability directly below.2) for a peg, use the average of the probabilities in the adjacent columns one row down.

这将简单地将概率传播到顶部，其中每个槽将被分配从该槽达到目标的概率。没有树，就没有递归。