diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/remove_boxes.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/remove_boxes.cpp')
-rw-r--r-- | other/remove_boxes.cpp | 40 |
1 files changed, 40 insertions, 0 deletions
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<int> &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<int> &boxes) { + int n = boxes.size(); + return dfs(boxes, 0, n - 1, 0); + } +}; + +int main() { + Solution obj; + vector<int> 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 +} |