91影视

Let us consider that n-1 coins are already tossed together and n^th coin is toss separately.

Now let $P\left(1...n,k\right)$ is the probability of getting exactly 鈥�k鈥� heads when 鈥�n 鈥� coins are tossed.

Now applying our consideration, we will define a storing table $n*k$and fill the various probability.

Thus there are two ways of getting exactly 鈥�k 鈥� heads with 鈥�n 鈥� coins:

• If $n-1$coins have $k$heads and $n$^th coin show tail.
• If $n-1$coins have $k-1$heads and $n$^th coin is head.

According to the above two cases, we can define our subproblem as:

$\mathbf{P}\left(n,k\right)\mathbf{=}\mathbf{P}\left(n-1,k\right)\mathbf{*}\left(1-p\left[n\right]\right)\mathbf{+}\mathbf{P}\left(n-1,k-1\right)\mathbf{*}\mathbf{p}\left[n\right]$

If we are tossing first $i$coins, where $j$is the number of heads,

And L(i,j) as total probability of getting head,

localid="1657267432115" $\mathbf{L}\left(i,j\right)\mathbf{=}\{\begin{array}{l}{P}_i*L\left(i-1,j-1\right)+\left(1-p_i\right)*L\left(i-1,j\right);\mathrm{for}j=0,1..i\\ 0;\mathrm{for}j鈮�0\end{array}$

On solving this recursion equation, the time complexity will be $0\left(nk\right)$.

This is because our algorithm will run for 鈥�n鈥� coins but will stop if it gets k heads. So we will be using first loop for to toss each coin which would be 鈥�n鈥� and then second loop will check for head in the tossed coin.