计数头 - 动态编程

Question

问题:

给定整数n和k,同时,你想要确定当有偏独立的硬币被随机抛出时获得精确头部的概率,其中p _i是第i ^个硬币出现头部的概率.为此任务提供O(n ²)算法.假设您可以在O(1)时间内在[0,1]中相乘并添加两个数字.p1,p2,..., pn; where pi ? [0, 1]kn

有人可以帮助我开发递归关系,以便我可以编码它.(问题来自于动态编程章节的背面练习"Algorithms by Dasgupta")

Answer 1

考虑将(n-1)个硬币一起投掷并将第n个硬币分开并考虑相互独立的情况.

结合更简单案例的概率得到P(1..n,k)(其中P(1..n,k)是n个硬币时获得正好k个头的概率)

然后应用此规则并填充NxK表中的所有单元格

编辑:

有两种可能的方法来获得n个硬币的k个头 -

a)如果(n-1)个硬币有k个头,第N个硬币是尾部,并且

b)如果(n-1)个硬币有k-1个头,第N个硬币是头

所以

P(n,k)= P(n-1,k)*(1-p [n])+ P(n-1,k-1)*p [n]