837.New 21 Game
===

###### tags: `Medium`,`Math`,`DP`,`Sliding Window`

[837. New 21 Game](https://leetcode.com/problems/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` <= 10^4^
* 1 <= `maxPts` <= 10^4^

### 解答

#### Python

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k - 1 + maxPts:
            return 1.0
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        prob, total = 0.0, 1.0
        for i in range(1, n + 1):
            dp[i] = total / maxPts
            if i < k:
                total += dp[i]
            else:
                prob += dp[i]
            if i >= maxPts:
                total -= dp[i - maxPts]
        return prob

> [name=Yen-Chi Chen][time=Thu, May 25, 2023]

#### C++

class Solution {
public:
    double new21Game(int targetPoint, int stopPoint, int maxPointPerDraw) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        double ans = 0.;
        if (stopPoint == 0 or targetPoint >= stopPoint + maxPointPerDraw) {
            return 1.;
        } 
        vector<double> probability(targetPoint + 1, 0);
        probability[0] = 1.;
        double slideWindowSum = 1.;
        for (int possiblePoint = 1; possiblePoint <= targetPoint; possiblePoint ++) {
            probability[possiblePoint] = slideWindowSum / maxPointPerDraw;
            if (possiblePoint < stopPoint) {
                slideWindowSum += probability[possiblePoint];
            } else {
                ans += probability[possiblePoint];
            }
            if (possiblePoint - maxPointPerDraw >= 0) {
                slideWindowSum -= probability[possiblePoint - maxPointPerDraw];
            }
        }
        return ans;
    }
};

> [name=Jerry Wu][time=Thu, May 25, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)