Counting Heads - Dynamic Programming

Question

Problem:

Given integers n and k, as well as p 1 ,p 2 ,..., p n ; where p i ε [0, 1] p 1 ,p 2 ,..., p n ; where p i ε [0, 1] , you want to determine the probability of getting exactly k heads when rejected coins n randomly thrown, where p _i is the probability that the coin i ^th appears up. Give an O (n ² ) algorithm for this task. Suppose you can multiply and add two numbers in [0, 1] O (1) times.

Can someone help me with developing a relapse relationship so that I can encode it. (The question comes from a previous exercise in the chapter Dynamic Programming in Dasgupta Algorithms)

Answer 1

Consider a situation where (n-1) coins are thrown together, and the nth coin is discarded and takes into account mutual independence.

Combine the probabilities of simpler cases to get P (1..n, k) (where P (1..n, k) is the probability of getting exactly k goals with n coins)

Then apply this rule and fill in all the cells in the NxK table

Edit:

There are two possible ways to get exactly k goals with n coins -

a) if (n-1) coins have k goals, and the Nth coin has a tail, and

b) if (n-1) coins have k-1 goals and the Nth head

So

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