HackMD
837.New 21 Game
tags: Medium,Math,DP,Sliding Window
題目描述
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
解答
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
