leetcode

commit 1976b8dcea2f7605b91c19e274f5ffe283d45a1f
parent 6f2d874f429bc33d870af050cd2d8bfd82a5b82e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  7 Dec 2024 13:14:00 +0100

1 Random Problem

Diffstat:
A
Problems/0546.cpp
 | 
27
+++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/Problems/0546.cpp b/Problems/0546.cpp
@@ -0,0 +1,27 @@
+class Solution {
+    static int dp[200][200][200];
+
+    static int rec(const vector<int> &boxes, int l, int r, int k) {
+        if (l > r) return 0;
+        if (dp[l][r][k] > 0) return dp[l][r][k];
+
+        int lOrg = l, kOrg = k;
+        while (l + 1 <= r && boxes[l] == boxes[l + 1])
+            l += 1, k += 1;
+
+        int ans = (k + 1) * (k + 1) + rec(boxes, l + 1, r, 0);
+        for (int m = l + 1; m <= r; ++m) {
+            if (boxes[m] != boxes[l]) continue;
+            ans = max(ans, rec(boxes, m, r, k + 1) + rec(boxes, l + 1, m - 1, 0));
+        }
+        return dp[lOrg][r][kOrg] = ans;
+    }
+
+  public:
+    int removeBoxes(const vector<int> &boxes) const {
+        memset(dp, 0x00, sizeof(dp));
+        return rec(boxes, 0, size(boxes) - 1, 0);
+    }
+};
+
+int Solution::dp[200][200][200];
diff --git a/README.md b/README.md
@@ -447,6 +447,7 @@ reference and a base for solving problems.
 |  0540  |   Medium   | [Single Element in a Sorted Array](Problems/0540.cpp)                                              |
 |  0542  |   Medium   | [01 Matrix](Problems/0542.cpp)                                                                     |
 |  0543  |    Easy    | [Diameter of Binary Tree](Problems/0543.cpp)                                                       |
+|  0546  |    Hard    | [Remove Boxes](Problems/0546.cpp)                                                                  |
 |  0547  |   Medium   | [Number of Provinces](Problems/0547.cpp)                                                           |
 |  0550  |   Medium   | [Game Play Analysis IV](Problems/0550.cpp)                                                         |
 |  0552  |    Hard    | [Student Attendance Record II](Problems/0552.cpp)                                                  |