From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/remove_boxes.cpp | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 other/remove_boxes.cpp (limited to 'other/remove_boxes.cpp') diff --git a/other/remove_boxes.cpp b/other/remove_boxes.cpp new file mode 100644 index 0000000..47f62a9 --- /dev/null +++ b/other/remove_boxes.cpp @@ -0,0 +1,40 @@ +// 546. Remove Boxes +#include "leetcode.h" + +/* + * given several 'boxes' with different colours represented by different + * positive numbers. you may experience several rounds to remove boxes until + * there is no box left. each time you can choose some continuous boxes with the + * same colour (ie. composed of 'k' boxes, 'k >= 1'), remove them and get 'k * + * k' points. return the maximum points you can get. + */ + +class Solution { + int dp[100][100][100] = {0}; + int dfs(vector &boxes, int i, int j, int k) { + if (j < i) + return 0; + if (dp[i][j][k]) + return dp[i][j][k]; + int res = (1 + k) * (1 + k) + dfs(boxes, i + 1, j, 0); + for (int m = i + 1; m <= j; m++) + if (boxes[m] == boxes[i]) + res = max(res, dfs(boxes, i + 1, m - 1, 0) + dfs(boxes, m, j, k + 1)); + dp[i][j][k] = res; + return res; + } + +public: + int removeBoxes(vector &boxes) { + int n = boxes.size(); + return dfs(boxes, 0, n - 1, 0); + } +}; + +int main() { + Solution obj; + vector b1 = {1, 3, 2, 2, 2, 3, 4, 3, 1}, b2 = {1, 1, 1}, b3 = {1}; + printf("%d\n", obj.removeBoxes(b1)); // expect: 23 + printf("%d\n", obj.removeBoxes(b2)); // expect: 9 + printf("%d\n", obj.removeBoxes(b3)); // expect: 1 +} -- cgit v1.2.3