首页 > 代码库 > How Many Boyfriends

How Many Boyfriends

知乎上看到一个问题,如果一个女人说自己集齐了12个星座的男朋友,那么她已经搞过多少男人了。

 

先考虑这个问题的最简单版本,如果说该女人每一次和12个星座的男人交往的概率相同。

考虑$dp$

注意到这个问题正向十分不好推(因为如果用f表示从开始到当前的状态的话,只能由当前f推到 对应拓扑图上后面的f)。

考虑从后面推到前面。

$f_n$ 表示已经搞了 $n$ 种男人,搞到12种男人的期望步数。

这样  $f_n = \frac{n}{12} f_n  + \frac{12-n}{12} f_{n+1} + 1$

化简得 $f_n = f_{n+1} + \frac{12}{12-n}$

这样有 $f_n = n H_n ≈ 37.285$ 个男人

 

How Many Boyfriends