leetcode

commit 2a72d609a5082614d3e554ea5d4fbc0d27d647e7
parent 87b75f390e210deb016066b80383bd623ca428ba
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 16 Sep 2024 20:41:38 +0200

1 Random Problem

Diffstat:
A
Problems/0375.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/0375.cpp b/Problems/0375.cpp
@@ -0,0 +1,23 @@
+class Solution {
+    static int dp[201][201];
+
+    static int rec(int a, int b) {
+        if (a >= b) return 0;
+        if (dp[a][b] != 0) return dp[a][b];
+
+        int res = INT_MAX;
+        for (int i = (a + b) / 2; i <= b; i++) {
+            res = min(i + max(rec(i + 1, b), rec(a, i - 1)), res);
+        }
+
+        return dp[a][b] = res;
+    }
+
+  public:
+    int getMoneyAmount(int n) const {
+        memset(dp, 0x00, sizeof(dp));
+        return rec(1, n);
+    }
+};
+
+int Solution::dp[201][201];
diff --git a/README.md b/README.md
@@ -296,6 +296,7 @@ for solving problems.
 |  0371  |   Medium   | [Sum of Two Integers](Problems/0371.cpp)                                                           |
 |  0373  |   Medium   | [Find K Pairs with Smallest Sums](Problems/0373.cpp)                                               |
 |  0374  |    Easy    | [Guess Number Higher or Lower](Problems/0374.cpp)                                                  |
+|  0375  |   Medium   | [Guess Number Higher or Lower II](Problems/0375.cpp)                                               |
 |  0376  |   Medium   | [Wiggle Subsequence](Problems/0376.cpp)                                                            |
 |  0377  |   Medium   | [Combination Sum IV](Problems/0377.cpp)                                                            |
 |  0378  |   Medium   | [Kth Smallest Element in a Sorted Matrix](Problems/0378.cpp)                                       |