# 837. New 21 Game

• Time: $O(n)$
• Space: $O(n)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: double new21Game(int n, int k, int maxPts) { // When the game ends, the point is in [k..k - 1 + maxPts] // P = 1, if n >= k - 1 + maxPts // P = 0, if n < k (note the constraints already have k <= n) if (k == 0 || n >= k - 1 + maxPts) return 1.0; double ans = 0.0; vector dp(n + 1); // dp[i] := prob to have i points dp[0] = 1.0; double windowSum = dp[0]; // P(i - 1) + P(i - 2) + ... + P(i - maxPts) for (int i = 1; i <= n; ++i) { // The prob to get point i is // P(i) = [P(i - 1) + P(i - 2) + ... + P(i - maxPts)] / maxPts dp[i] = windowSum / maxPts; if (i < k) windowSum += dp[i]; else // The game ends ans += dp[i]; if (i - maxPts >= 0) windowSum -= dp[i - maxPts]; } return ans; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public double new21Game(int n, int k, int maxPts) { // When the game ends, the point is in [k..k - 1 + maxPts] // P = 1, if n >= k - 1 + maxPts // P = 0, if n < k (note the constraints already have k <= n) if (k == 0 || n >= k - 1 + maxPts) return 1.0; double ans = 0.0; double[] dp = new double[n + 1]; // dp[i] := prob to have i points dp[0] = 1.0; double windowSum = dp[0]; // P(i - 1) + P(i - 2) + ... + P(i - maxPts) for (int i = 1; i <= n; ++i) { // The prob to get point i is // P(i) = [P(i - 1) + P(i - 2) + ... + P(i - maxPts)] / maxPts dp[i] = windowSum / maxPts; if (i < k) windowSum += dp[i]; else // The game ends ans += dp[i]; if (i - maxPts >= 0) windowSum -= dp[i - maxPts]; } return ans; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float: # When the game ends, the point is in [k..k - 1 + maxPts] # P = 1, if n >= k - 1 + maxPts # P = 0, if n < k (note the constraints already have k <= n) if k == 0 or n >= k - 1 + maxPts: return 1.0 ans = 0.0 dp = [1.0] + [0] * n # dp[i] := prob to have i points windowSum = dp[0] # P(i - 1) + P(i - 2) + ... + P(i - maxPts) for i in range(1, n + 1): # The prob to get point i is # P(i) = [P(i - 1) + P(i - 2) + ... + P(i - maxPts)] / maxPts dp[i] = windowSum / maxPts if i < k: windowSum += dp[i] else: # The game ends ans += dp[i] if i - maxPts >= 0: windowSum -= dp[i - maxPts] return ans