837.New 21 Game

tags: Medium,Math,DP,Sliding Window

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 <= 10⁴
• 1 <= maxPts <= 10⁴

解答

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

Yen-Chi ChenThu, 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;
    }
};

Jerry WuThu, May 25, 2023

Reference

回到題目列表