## 837. New 21 Game

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, W]`

, where `W`

is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets `K`

or more points. What is the probability that she has `N`

or less points?

**Example 1:**

Input:N = 10, K = 1, W = 10Output:1.00000Explanation:Alice gets a single card, then stops.

**Example 2:**

Input:N = 6, K = 1, W = 10Output:0.60000Explanation:Alice gets a single card, then stops. In 6 out of W = 10 possibilities, she is at or below N = 6 points.

**Example 3:**

Input:N = 21, K = 17, W = 10Output:0.73278

**Note:**

`0 <= K <= N <= 10000`

`1 <= W <= 10000`

- Answers will be accepted as correct if they are within
`10^-5`

of the correct answer. - The judging time limit has been reduced for this question.

## Rust Solution

```
struct Solution;
impl Solution {
fn new21_game(n: i32, k: i32, w: i32) -> f64 {
if k == 0 || n > k + w {
return 1.0;
}
let n = n as usize;
let w = w as usize;
let k = k as usize;
let mut dp: Vec<f64> = vec![0.0; n + 1];
dp[0] = 1.0;
let mut sum = 1.0;
let mut res = 0.0;
for i in 1..=n {
dp[i] = sum / w as f64;
if i < k {
sum += dp[i];
} else {
res += dp[i];
}
if i >= w {
sum -= dp[i - w];
}
}
res
}
}
#[test]
fn test() {
use assert_approx_eq::assert_approx_eq;
let n = 10;
let k = 1;
let w = 10;
let res = 1.0;
assert_approx_eq!(Solution::new21_game(n, k, w), res);
let n = 6;
let k = 1;
let w = 10;
let res = 0.6;
assert_approx_eq!(Solution::new21_game(n, k, w), res);
let n = 21;
let k = 17;
let w = 10;
let res = 0.732777;
assert_approx_eq!(Solution::new21_game(n, k, w), res);
}
```

Having problems with this solution? Click here to submit an issue on github.