## Algorithm

Problem Name: 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, 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`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const new21Game = function(N, K, W) {
if (K === 0 || N >= K + W) {
return 1;
}
const dp = [];
let Wsum = 1;
let res = 0;
dp = 1;
for (let i = 1; i <= N; i++) {
dp[i] = Wsum / W;
if (i < K) {
Wsum += dp[i];
} else {
res += dp[i];
}
if (i - W >= 0) {
Wsum -= dp[i - W];
}
}
return res;
};

console.log(new21Game(6, 1, 10));
console.log(new21Game(10, 1, 10));
console.log(new21Game(21, 17, 10));
``````
Copy The Code &

Input

cmd
n = 6, k = 1, maxPts = 10

Output

cmd
0.60000

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def new21Game(self, N, K, W):
if K == 0 or N >= K + W: return 1
dp = [1.0] + [0.0] * N
Wsum, res = 1.0, 0.0
for i in range(1, N + 1):
dp[i] += Wsum / W
if i < K: Wsum += dp[i]
else: res += dp[i]
if i - W >= 0: Wsum -= dp[i - W]
return res
``````
Copy The Code &

Input

cmd
n = 6, k = 1, maxPts = 10

Output

cmd
0.60000

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0837_New21Game
{
public double New21Game(int N, int K, int W)
{
var dp = new double[N + W + 1];
for (int k = K; k <= N; k++)
dp[k] = 1.0;

double S = Math.Min(W, N - K + 1);
for (int k = K - 1; k >= 0; k--)
{
dp[k] = S / W;
S += dp[k] - dp[k + W];
}

return dp;
}
}
}
``````
Copy The Code &

Input

cmd
n = 10, k = 1, maxPts = 10

Output

cmd
1.00000