Array
Math
Dynamic Programming
Probability and Statistics
Description
You have some coins. The i
-th coin has a probability prob[i]
of facing heads when tossed.
Return the probability that the number of coins facing heads equals target
if you toss every coin exactly once.
Example 1:
Input: prob = [0.4], target = 1
Output: 0.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125
Constraints:
1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target
<= prob.length
Answers will be accepted as correct if they are within 10^-5
of the correct answer.
Solutions
Solution 1: Dynamic Programming
Let $f[i][j]$ represent the probability of having $j$ coins facing up in the first $i$ coins, and initially $f[0][0]=1$. The answer is $f[n][target]$.
Consider $f[i][j]$, where $i \geq 1$. If the current coin is facing down, then $f[i][j] = (1 - p) \times f[i - 1][j]$; If the current coin is facing up and $j \gt 0$, then $f[i][j] = p \times f[i - 1][j - 1]$. Therefore, the state transition equation is:
$$
f[i][j] = \begin{cases}
(1 - p) \times f[i - 1][j], & j = 0 \
(1 - p) \times f[i - 1][j] + p \times f[i - 1][j - 1], & j \gt 0
\end{cases}
$$
where $p$ represents the probability of the $i$-th coin facing up.
We note that the state $f[i][j]$ is only related to $f[i - 1][j]$ and $f[i - 1][j - 1]$, so we can optimize the two-dimensional space into one-dimensional space.
The time complexity is $O(n \times target)$, and the space complexity is $O(target)$. Where $n$ is the number of coins.
Python3 Java C++ Go TypeScript
class Solution :
def probabilityOfHeads ( self , prob : List [ float ], target : int ) -> float :
n = len ( prob )
f = [[ 0 ] * ( target + 1 ) for _ in range ( n + 1 )]
f [ 0 ][ 0 ] = 1
for i , p in enumerate ( prob , 1 ):
for j in range ( min ( i , target ) + 1 ):
f [ i ][ j ] = ( 1 - p ) * f [ i - 1 ][ j ]
if j :
f [ i ][ j ] += p * f [ i - 1 ][ j - 1 ]
return f [ n ][ target ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public double probabilityOfHeads ( double [] prob , int target ) {
int n = prob . length ;
double [][] f = new double [ n + 1 ][ target + 1 ] ;
f [ 0 ][ 0 ] = 1 ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j <= Math . min ( i , target ); ++ j ) {
f [ i ][ j ] = ( 1 - prob [ i - 1 ] ) * f [ i - 1 ][ j ] ;
if ( j > 0 ) {
f [ i ][ j ] += prob [ i - 1 ] * f [ i - 1 ][ j - 1 ] ;
}
}
}
return f [ n ][ target ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
double probabilityOfHeads ( vector < double >& prob , int target ) {
int n = prob . size ();
double f [ n + 1 ][ target + 1 ];
memset ( f , 0 , sizeof ( f ));
f [ 0 ][ 0 ] = 1 ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 0 ; j <= min ( i , target ); ++ j ) {
f [ i ][ j ] = ( 1 - prob [ i - 1 ]) * f [ i - 1 ][ j ];
if ( j > 0 ) {
f [ i ][ j ] += prob [ i - 1 ] * f [ i - 1 ][ j - 1 ];
}
}
}
return f [ n ][ target ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func probabilityOfHeads ( prob [] float64 , target int ) float64 {
n := len ( prob )
f := make ([][] float64 , n + 1 )
for i := range f {
f [ i ] = make ([] float64 , target + 1 )
}
f [ 0 ][ 0 ] = 1
for i := 1 ; i <= n ; i ++ {
for j := 0 ; j <= i && j <= target ; j ++ {
f [ i ][ j ] = ( 1 - prob [ i - 1 ]) * f [ i - 1 ][ j ]
if j > 0 {
f [ i ][ j ] += prob [ i - 1 ] * f [ i - 1 ][ j - 1 ]
}
}
}
return f [ n ][ target ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function probabilityOfHeads ( prob : number [], target : number ) : number {
const n = prob . length ;
const f = new Array ( n + 1 ). fill ( 0 ). map (() => new Array ( target + 1 ). fill ( 0 ));
f [ 0 ][ 0 ] = 1 ;
for ( let i = 1 ; i <= n ; ++ i ) {
for ( let j = 0 ; j <= target ; ++ j ) {
f [ i ][ j ] = f [ i - 1 ][ j ] * ( 1 - prob [ i - 1 ]);
if ( j ) {
f [ i ][ j ] += f [ i - 1 ][ j - 1 ] * prob [ i - 1 ];
}
}
}
return f [ n ][ target ];
}
Solution 2
Python3 Java C++ Go TypeScript
class Solution :
def probabilityOfHeads ( self , prob : List [ float ], target : int ) -> float :
f = [ 0 ] * ( target + 1 )
f [ 0 ] = 1
for p in prob :
for j in range ( target , - 1 , - 1 ):
f [ j ] *= 1 - p
if j :
f [ j ] += p * f [ j - 1 ]
return f [ target ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public double probabilityOfHeads ( double [] prob , int target ) {
double [] f = new double [ target + 1 ] ;
f [ 0 ] = 1 ;
for ( double p : prob ) {
for ( int j = target ; j >= 0 ; -- j ) {
f [ j ] *= ( 1 - p );
if ( j > 0 ) {
f [ j ] += p * f [ j - 1 ] ;
}
}
}
return f [ target ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public :
double probabilityOfHeads ( vector < double >& prob , int target ) {
double f [ target + 1 ];
memset ( f , 0 , sizeof ( f ));
f [ 0 ] = 1 ;
for ( double p : prob ) {
for ( int j = target ; j >= 0 ; -- j ) {
f [ j ] *= ( 1 - p );
if ( j > 0 ) {
f [ j ] += p * f [ j - 1 ];
}
}
}
return f [ target ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13 func probabilityOfHeads ( prob [] float64 , target int ) float64 {
f := make ([] float64 , target + 1 )
f [ 0 ] = 1
for _ , p := range prob {
for j := target ; j >= 0 ; j -- {
f [ j ] *= ( 1 - p )
if j > 0 {
f [ j ] += p * f [ j - 1 ]
}
}
}
return f [ target ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13 function probabilityOfHeads ( prob : number [], target : number ) : number {
const f = new Array ( target + 1 ). fill ( 0 );
f [ 0 ] = 1 ;
for ( const p of prob ) {
for ( let j = target ; j >= 0 ; -- j ) {
f [ j ] *= 1 - p ;
if ( j > 0 ) {
f [ j ] += f [ j - 1 ] * p ;
}
}
}
return f [ target ];
}
GitHub