{"id":3413,"date":"2018-08-02T21:06:05","date_gmt":"2018-08-03T04:06:05","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3413"},"modified":"2018-08-03T23:14:27","modified_gmt":"2018-08-04T06:14:27","slug":"leetcode-546-remove-boxes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-546-remove-boxes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 546. Remove Boxes"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 546 Remove Boxes  - \u5237\u9898\u627e\u5de5\u4f5c EP214\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/wT7aS5fHZhs?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Given several boxes with different colors represented by different positive numbers.<br \/>\nYou may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k &gt;= 1), remove them and get\u00a0<code>k*k<\/code>\u00a0points.<br \/>\nFind the maximum points you can get.<\/p>\n<p><b>Example 1:<\/b><br \/>\nInput:<\/p>\n<pre>[1, 3, 2, 2, 2, 3, 4, 3, 1]\r\n<\/pre>\n<p>Output:<\/p>\n<pre>23\r\n<\/pre>\n<p>Explanation:<\/p>\n<pre class=\"crayon:false\">[1, 3, 2, 2, 2, 3, 4, 3, 1] \r\n----&gt; [1, 3, 3, 4, 3, 1] (3*3=9 points) \r\n----&gt; [1, 3, 3, 3, 1] (1*1=1 points) \r\n----&gt; [1, 1] (3*3=9 points) \r\n----&gt; [] (2*2=4 points)\r\n<\/pre>\n<p><b>Note:<\/b>\u00a0The number of boxes\u00a0<code>n<\/code>\u00a0would not exceed 100.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3425\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3426\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/546-ep214-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1>Solution: Recursion + Memorization<\/h1>\n<p>Use dp[l][r][k] to denote the max score of subarray box[l] ~ box[r] with k boxes after box[r] that have the same color as box[r]<\/p>\n<p><span style=\"color: #ff0000;\">box[l]<\/span>, <span style=\"color: #339966;\">box[l+1]<\/span>, &#8230;, <span style=\"color: #0000ff;\">box[r], box[r+1], &#8230;, box[r+k]<\/span><\/p>\n<p>e.g. &#8220;CDABACAAAAA&#8221;<\/p>\n<p>dp[2][6][4] is the max score of\u00a0[ABACA] followed by [AAAA]<br \/>\ndp[2][6][3] is the max score of\u00a0[ABACA] followed by [AAA]<\/p>\n<pre class=\"crayon:false\">base case: l &gt; r, empty array, return 0.<\/pre>\n<pre class=\"crayon:false \">Transition:\r\ndp[l][r][k] = max(dp[l][r-1][0] + (k + 1)*(k + 1),\u00a0 # case 1\r\n                  dp[l][i][k+1] + dp[i+1][r-1][0])  # case 2\r\n# \"ABACA|AAAA\" \r\n# case 1: dp(\"ABAC\") + score(\"AAAAA\") drop j and the tail.\r\n# case 2: box[i] == box[r], l &lt;= i &lt; r, try all break points\r\n# max({dp(\"A|AAAAA\") + dp(\"BAC\")}, {dp(\"ABA|AAAAA\") + dp(\"C\")})<\/pre>\n<p>Time complexity: O(n^4)<\/p>\n<p>Space complexity: O(n^3)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 196 ms\r\nclass Solution {\r\npublic:\r\n  int removeBoxes(vector&lt;int&gt;&amp; boxes) {\r\n    const int n = boxes.size();\r\n    m_ = vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;(n, vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(n)));\r\n    return dfs(boxes, 0, n - 1, 0);\r\n  }\r\nprivate:\r\n  vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt; m_;\r\n  \r\n  int dfs(const vector&lt;int&gt;&amp; boxes, int l, int r, int k) {\r\n    if (l &gt; r) return 0;    \r\n    if (m_[l][r][k] &gt; 0) return m_[l][r][k];\r\n    m_[l][r][k] = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);\r\n    for (int i = l; i &lt; r; ++i)\r\n      if (boxes[i] == boxes[r])\r\n        m_[l][r][k] = max(m_[l][r][k], dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));\r\n    return m_[l][r][k];\r\n  }\r\n};<\/pre>\n<p>Optimized<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nint m[100][100][100];\r\nclass Solution {\r\npublic:\r\n  int removeBoxes(vector&lt;int&gt;&amp; boxes) {    \r\n    memset(m, 0, sizeof(m));\r\n    return dfs(boxes, 0, boxes.size() - 1, 0);\r\n  }\r\nprivate:\r\n  int dfs(const vector&lt;int&gt;&amp; boxes, int l, int r, int k) {\r\n    if (l &gt; r) return 0;    \r\n    if (m[l][r][k] &gt; 0) return m[l][r][k];\r\n    int rr = r;\r\n    int kk = k;\r\n    while (l &lt; r &amp;&amp; boxes[r - 1] == boxes[r]) {--r; ++k;}\r\n    m[l][r][k] = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);\r\n    for (int i = l; i &lt; r; ++i)\r\n      if (boxes[i] == boxes[r])\r\n        m[l][r][k] = max(m[l][r][k], dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));\r\n    for (int d = 1; d &lt;= r - rr; ++d)\r\n      m[l][r + d][k - d] = m[l][r][k];\r\n    return m[l][r][k];\r\n  }\r\n};<\/pre>\n<p>Use a HashTable to replace the 3D DP array since the DP array could be sparse when many consecutive boxes are the same color.<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms (beats 100%)\r\nclass Solution {\r\npublic:\r\n  int removeBoxes(vector&lt;int&gt;&amp; boxes) {\r\n    len_ = vector&lt;int&gt;(boxes.size());\r\n    for (int i = 1; i &lt; boxes.size(); ++i)\r\n      if (boxes[i] == boxes[i - 1]) len_[i] = len_[i - 1] + 1;\r\n    return dfs(boxes, 0, boxes.size() - 1, 0);\r\n  }\r\nprivate:\r\n  unordered_map&lt;int, int&gt; m_;\r\n  vector&lt;int&gt; len_;\r\n  int dfs(const vector&lt;int&gt;&amp; boxes, int l, int r, int k) {\r\n    if (l &gt; r) return 0;\r\n    k += len_[r];\r\n    r -= len_[r];\r\n    int key = (l * 100 + r) * 100 + k;\r\n    auto it = m_.find(key);\r\n    if (it != m_.end()) return it-&gt;second;    \r\n    int&amp; ans = m_[key];\r\n    ans = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);\r\n    for (int i = l; i &lt; r; ++i)\r\n      if (boxes[i] == boxes[r])\r\n        ans = max(ans, dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));\r\n    return ans;\r\n  }\r\n};<\/pre>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-312-burst-balloons\/\">\u82b1\u82b1\u9171 LeetCode 312. Burst Balloons<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-488-zuma-game\/\">\u82b1\u82b1\u9171 LeetCode 488. Zuma Game<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,361],"class_list":["post-3413","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-on4","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3413","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3413"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3413\/revisions"}],"predecessor-version":[{"id":3428,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3413\/revisions\/3428"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3413"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3413"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3413"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}