algorithm - 计数头 - 动态规划

Question

问题:

Given integers n and k, along with p<sub>1</sub>,p<sub>2</sub>,..., p<sub>n</sub>; where p<sub>i</sub> ε [0, 1], you want to determine the probability of obtaining exactly k heads when n biased coins are tossed independently at random, where p_i is the probability that the i^th coin comes up heads. Give an O(n²) algorithm for this task. Assume you can multiply and add two numbers in [0, 1] in O(1) time.

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