leetcode

commit 960f0123c61a6781c3a413ff7816f7ccd8ecf0c4
parent 8cebc5b3bd2dde4dd66a57c09c56a44c958de2d8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 25 May 2023 22:33:40 +0200

Daily Problem

Diffstat:
A
Problems/0837.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 18 insertions(+), 0 deletions(-)
diff --git a/Problems/0837.cpp b/Problems/0837.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+  double new21Game(int n, int k, int maxPts) {
+    if (k == 0 || n >= k + maxPts) return 1.0;
+    vector<double> dp(n + 1);
+    double sum = 1.0, ans = 0.0;
+
+    dp[0] = 1.0;
+    for (int i = 1; i < n + 1; i++) {
+      dp[i] = sum / maxPts;
+      (i < k ? sum : ans) += dp[i];
+      if (i - maxPts >= 0) sum -= dp[i - maxPts];
+    }
+
+    return ans;
+  }
+};
diff --git a/README.md b/README.md
@@ -346,6 +346,7 @@ for solving problems.
 |  0802  |   Medium   | [Find Eventual Safe States](Problems/0802.cpp)                                                   |
 |  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                  |
 |  0830  |   Medium   | [Kth Smallest Element in a BST](Problems/0230.cpp)                                               |
+|  0837  |   Medium   | [New 21 Game](Problems/0837.cpp)                                                                 |
 |  0839  |    Hard    | [Similar String Groups](Problems/0839.cpp)                                                       |
 |  0841  |   Medium   | [Keys and Rooms](Problems/0841.cpp)                                                              |
 |  0844  |    Easy    | [Backspace String Compare](Problems/0844.cpp)                                                    |