leetcode

commit 53bb1f937d3a913ec83528296036ff2a1381f2fa
parent 1827090201cbe1958739682b78b1764783ae02c7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu,  1 Feb 2024 22:08:11 +0000

1 Daily Problem

Diffstat:
A
Problems/1049.cpp
 | 
14
++++++++++++++
M
README.md
 | 
1
+

2 files changed, 15 insertions(+), 0 deletions(-)
diff --git a/Problems/1049.cpp b/Problems/1049.cpp
@@ -0,0 +1,14 @@
+class Solution {
+    static int dp[6001][31];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int lastStoneWeightII(const vector<int> &stones, int total = 0, int crnt = 0) const {
+        if (crnt == size(stones)) return total >= 0 ? total : INT_MAX;
+        if (dp[total + 3000][crnt] != -1) return dp[total + 3000][crnt];
+        return dp[total + 3000][crnt] = min(lastStoneWeightII(stones, total + stones[crnt], crnt + 1),
+                                            lastStoneWeightII(stones, total - stones[crnt], crnt + 1));
+    }
+};
+
+int Solution::dp[6001][31];
diff --git a/README.md b/README.md
@@ -595,6 +595,7 @@ for solving problems.
 |  1046  |    Easy    | [Last Stone Weight](Problems/1046.cpp)                                                             |
 |  1047  |    Easy    | [Remove All Adjacent Duplicates In String](Problems/1047.cpp)                                      |
 |  1048  |   Medium   | [Longest String Chain](Problems/1048.cpp)                                                          |
+|  1049  |   Medium   | [Last Stone Weight II](Problems/1049.cpp)                                                          |
 |  1050  |    Easy    | [Actors and Directors Who Cooperated At Least Three Times](Problems/1050.cpp)                      |
 |  1051  |    Easy    | [Height Checker](Problems/1051.cpp)                                                                |
 |  1052  |   Medium   | [Grumpy Bookstore Owner](Problems/1052.cpp)                                                        |