首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。