algorithm - 计数头 - 动态规划

Question

问题：

给定整数 n 和 k 以及，您想要确定当有偏硬币被随机独立抛掷时，准确获得正面的概率，其中 p _i是第 i^个硬币正面朝上的概率。给出这个任务的 O(n ² ) 算法。假设您可以在 O(1) 时间内将 [0, 1] 中的两个数字相乘和相加。p1,p2,..., pn; where pi ε [0, 1]kn

有人可以帮助我开发递归关系，以便我可以对其进行编码。（问题来自“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]