Math
Dynamic Programming
Sliding Window
Probability and Statistics
Description
Alice plays the following game, loosely based on the card game "21" .
Alice starts with 0
points and draws numbers while she has less than k
points. During each draw, she gains an integer number of points randomly from the range [1, maxPts]
, where maxPts
is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets k
or more points .
Return the probability that Alice has n
or fewer points.
Answers within 10-5
of the actual answer are considered accepted.
Example 1:
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Example 2:
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
Example 3:
Input: n = 21, k = 17, maxPts = 10
Output: 0.73278
Constraints:
0 <= k <= n <= 104
1 <= maxPts <= 104
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def new21Game ( self , n : int , k : int , maxPts : int ) -> float :
@cache
def dfs ( i : int ) -> float :
if i >= k :
return int ( i <= n )
if i == k - 1 :
return min ( n - k + 1 , maxPts ) / maxPts
return dfs ( i + 1 ) + ( dfs ( i + 1 ) - dfs ( i + maxPts + 1 )) / maxPts
return dfs ( 0 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
private double [] f ;
private int n , k , maxPts ;
public double new21Game ( int n , int k , int maxPts ) {
f = new double [ k ] ;
this . n = n ;
this . k = k ;
this . maxPts = maxPts ;
return dfs ( 0 );
}
private double dfs ( int i ) {
if ( i >= k ) {
return i <= n ? 1 : 0 ;
}
if ( i == k - 1 ) {
return Math . min ( n - k + 1 , maxPts ) * 1.0 / maxPts ;
}
if ( f [ i ] != 0 ) {
return f [ i ] ;
}
return f [ i ] = dfs ( i + 1 ) + ( dfs ( i + 1 ) - dfs ( i + maxPts + 1 )) / maxPts ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
double new21Game ( int n , int k , int maxPts ) {
vector < double > f ( k );
function < double ( int ) > dfs = [ & ]( int i ) -> double {
if ( i >= k ) {
return i <= n ? 1 : 0 ;
}
if ( i == k - 1 ) {
return min ( n - k + 1 , maxPts ) * 1.0 / maxPts ;
}
if ( f [ i ]) {
return f [ i ];
}
return f [ i ] = dfs ( i + 1 ) + ( dfs ( i + 1 ) - dfs ( i + maxPts + 1 )) / maxPts ;
};
return dfs ( 0 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func new21Game ( n int , k int , maxPts int ) float64 {
f := make ([] float64 , k )
var dfs func ( int ) float64
dfs = func ( i int ) float64 {
if i >= k {
if i <= n {
return 1
}
return 0
}
if i == k - 1 {
return float64 ( min ( n - k + 1 , maxPts )) / float64 ( maxPts )
}
if f [ i ] > 0 {
return f [ i ]
}
f [ i ] = dfs ( i + 1 ) + ( dfs ( i + 1 ) - dfs ( i + maxPts + 1 )) / float64 ( maxPts )
return f [ i ]
}
return dfs ( 0 )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 function new21Game ( n : number , k : number , maxPts : number ) : number {
const f = new Array ( k ). fill ( 0 );
const dfs = ( i : number ) : number => {
if ( i >= k ) {
return i <= n ? 1 : 0 ;
}
if ( i === k - 1 ) {
return Math . min ( n - k + 1 , maxPts ) / maxPts ;
}
if ( f [ i ] !== 0 ) {
return f [ i ];
}
return ( f [ i ] = dfs ( i + 1 ) + ( dfs ( i + 1 ) - dfs ( i + maxPts + 1 )) / maxPts );
};
return dfs ( 0 );
}
Solution 2
Python3 Java C++ Go TypeScript
class Solution :
def new21Game ( self , n : int , k : int , maxPts : int ) -> float :
f = [ 0 ] * ( k + maxPts )
for i in range ( k , min ( n + 1 , k + maxPts )):
f [ i ] = 1
f [ k - 1 ] = min ( n - k + 1 , maxPts ) / maxPts
for i in range ( k - 2 , - 1 , - 1 ):
f [ i ] = f [ i + 1 ] + ( f [ i + 1 ] - f [ i + maxPts + 1 ]) / maxPts
return f [ 0 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public double new21Game ( int n , int k , int maxPts ) {
if ( k == 0 ) {
return 1.0 ;
}
double [] f = new double [ k + maxPts ] ;
for ( int i = k ; i < Math . min ( n + 1 , k + maxPts ); ++ i ) {
f [ i ] = 1 ;
}
f [ k - 1 ] = Math . min ( n - k + 1 , maxPts ) * 1.0 / maxPts ;
for ( int i = k - 2 ; i >= 0 ; -- i ) {
f [ i ] = f [ i + 1 ] + ( f [ i + 1 ] - f [ i + maxPts + 1 ] ) / maxPts ;
}
return f [ 0 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
double new21Game ( int n , int k , int maxPts ) {
if ( k == 0 ) {
return 1.0 ;
}
double f [ k + maxPts ];
memset ( f , 0 , sizeof ( f ));
for ( int i = k ; i < min ( n + 1 , k + maxPts ); ++ i ) {
f [ i ] = 1 ;
}
f [ k - 1 ] = min ( n - k + 1 , maxPts ) * 1.0 / maxPts ;
for ( int i = k - 2 ; i >= 0 ; -- i ) {
f [ i ] = f [ i + 1 ] + ( f [ i + 1 ] - f [ i + maxPts + 1 ]) / maxPts ;
}
return f [ 0 ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 func new21Game ( n int , k int , maxPts int ) float64 {
if k == 0 {
return 1
}
f := make ([] float64 , k + maxPts )
for i := k ; i < min ( n + 1 , k + maxPts ); i ++ {
f [ i ] = 1
}
f [ k - 1 ] = float64 ( min ( n - k + 1 , maxPts )) / float64 ( maxPts )
for i := k - 2 ; i >= 0 ; i -- {
f [ i ] = f [ i + 1 ] + ( f [ i + 1 ] - f [ i + maxPts + 1 ]) / float64 ( maxPts )
}
return f [ 0 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function new21Game ( n : number , k : number , maxPts : number ) : number {
if ( k === 0 ) {
return 1 ;
}
const f = new Array ( k + maxPts ). fill ( 0 );
for ( let i = k ; i < Math . min ( n + 1 , k + maxPts ); ++ i ) {
f [ i ] = 1 ;
}
f [ k - 1 ] = Math . min ( n - k + 1 , maxPts ) / maxPts ;
for ( let i = k - 2 ; i >= 0 ; -- i ) {
f [ i ] = f [ i + 1 ] + ( f [ i + 1 ] - f [ i + maxPts + 1 ]) / maxPts ;
}
return f [ 0 ];
}