{"id":4423,"date":"2018-12-09T17:14:18","date_gmt":"2018-12-10T01:14:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4423"},"modified":"2018-12-12T00:05:27","modified_gmt":"2018-12-12T08:05:27","slug":"leetcode-956-tallest-billboard","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-956-tallest-billboard\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 956. Tallest Billboard"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 956. Tallest Billboard (1\/2) - \u5237\u9898\u627e\u5de5\u4f5c EP234\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/iPRWkifQgoo?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<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 956. Tallest Billboard (2\/2) - \u5237\u9898\u627e\u5de5\u4f5c EP234\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/WqLslW2sFxU?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>You are installing a billboard and want it to have the largest height.\u00a0 The billboard will have two steel supports, one on each side.\u00a0 Each steel support must be an equal height.<\/p>\n<p>You have a collection of\u00a0<code>rods<\/code>\u00a0which can be welded together.\u00a0 For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.<\/p>\n<p>Return the largest possible height of your billboard installation.\u00a0 If you cannot support the billboard, return 0.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[1,2,3,6]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">6<\/span>\r\n<strong>Explanation:<\/strong> We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-2-1\">[1,2,3,4,5,6]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-2\">10<\/span>\r\n<strong>Explanation:<\/strong> We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.\r\n<\/pre>\n<p><strong>Example 3:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-3-1\">[1,2]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-3\">0<\/span>\r\n<strong>Explanation: <\/strong>The billboard cannot be supported, so we return 0.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>0 &lt;= rods.length &lt;= 20<\/code><\/li>\n<li><code>1 &lt;= rods[i] &lt;= 1000<\/code><\/li>\n<li><code>The sum of rods is at most 5000.<\/code><\/li>\n<\/ol>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>\u5982\u679c\u76f4\u63a5<strong>\u66b4\u529b\u641c\u7d22<\/strong>\u7684\u8bdd\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(3^N)\uff0c\u94c1\u5b9a\u8d85\u65f6\u3002\u5bf9\u4e8e\u6bcf\u4e00\u6839\u6211\u4eec\u53ef\u4ee5\u9009\u62e91\u3001\u653e\u5230\u5de6\u8fb9\uff0c2\u3001\u653e\u5230\u53f3\u8fb9\uff0c3\u3001\u4e0d\u4f7f\u7528\u3002\u6700\u540e\u518d\u770b\u4e00\u4e0b\u5de6\u8fb9\u548c\u53f3\u8fb9\u662f\u5426\u76f8\u540c\u3002<\/p>\n<p>\u9898\u76ee\u7684\u6570\u636e\u89c4\u6a21\u4e2d\u7684\u8fd9\u53e5\u8bdd\u975e\u5e38\u91cd\u8981\uff1a<\/p>\n<p><code>The sum of rods is at most 5000.<\/code><\/p>\n<p>\u8fd9\u53e5\u8bdd\u5c31\u662f\u544a\u8bc9\u4f60\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548csum of rods\u6709\u5173\u7cfb\uff0c\u901a\u5e38\u9700\u8981\u4f7f\u7528DP\u3002<\/p>\n<p>\u7531\u4e8e\u6bcf\u6839\u67f1\u5b50\u53ea\u80fd\u4f7f\u7528\u4e00\u6b21\uff08\u8ba9\u6211\u4eec\u60f3\u5230\u4e86 \u56de\u590d\u00a0<strong>01\u80cc\u5305<\/strong>\uff09\uff0c\u4f46\u662f\u6211\u4eec\u600e\u4e48\u53bb\u63cf\u8ff0\u653e\u5230\u5de6\u8fb9\u8fd8\u662f\u653e\u5230\u53f3\u8fb9\u5462\uff1f<\/p>\n<p>Naive\u7684\u65b9\u6cd5\u662f\u7528 dp[i] \u8868\u793a\u4f7f\u7528\u524di\u4e2a\u67f1\u5b50\u80fd\u591f\u6784\u6210\u7684\u67f1\u5b50\u9ad8\u5ea6\u7684\u96c6\u5408\u3002<\/p>\n<p>e.g. dp[i] = {(h1, h2)},\u00a0 h1 &lt;= h2<\/p>\n<p>\u548c\u66b4\u529b\u641c\u7d22\u6bd4\u8d77\u6765DP\u5df2\u7ecf\u5bf9\u72b6\u6001\u8fdb\u884c\u4e86\u538b\u7f29\uff0c\u56e0\u4e3a\u6211\u5e76\u4e0d\u9700\u8981\u5173\u5fc3h1, h2\u662f\u901a\u8fc7\u54ea\u4e9b\uff08\u5728\u6211\u4e4b\u524d\u7684\uff09\u67f1\u5b50\u6784\u6210\u4e86\uff0c\u6211\u53ea\u5173\u5fc3\u5b83\u4eec\u7684\u5f53\u524d\u9ad8\u5ea6\u3002<\/p>\n<p>\u7136\u540e\u6211\u53ef\u4ee5\u9009\u62e9<\/p>\n<p>1\u3001\u4e0d\u7528\u7b2ci\u6839\u67f1\u5b50<\/p>\n<p>2\u3001\u653e\u5230\u4f4e\u7684\u90a3\u4e00\u5806<\/p>\n<p>3\u3001\u653e\u5230\u9ad8\u7684\u90a3\u4e00\u5806<\/p>\n<p>\u72b6\u6001\u8f6c\u79fb\u7684\u4f2a\u4ee3\u7801\uff1a<\/p>\n<p>for h1, h2 in dp[i &#8211; 1]:<\/p>\n<p>dp[i] += (h1, h2)\u00a0 \u00a0 \u00a0 \u00a0 # not used<\/p>\n<p>dp[i] += (h1, h2 + h)\u00a0 # put on higher<\/p>\n<p>if h1 + h &lt; h2:<\/p>\n<p>dp[i] += (h1 + h, h2)\u00a0 # put on lower<\/p>\n<p>else:<\/p>\n<p>dp[i] += (h2, h1 + h)\u00a0 # put on lower<\/p>\n<p>\u5047\u8bbe rods=[1,1,2]<\/p>\n<p>dp[0] = {(0,0)}<\/p>\n<p>dp[1] = {(0,0), (0,1)}<\/p>\n<p>dp[2] = {(0,0), (0,1), (0,2),\u00a0<strong>(1,1)<\/strong>}<\/p>\n<p>dp[3] = {(0,0), (0,1), (0,2), (0,3), (0,4), (1,1), (1,2), (1,3),\u00a0<strong>(2,2)<\/strong>}<\/p>\n<p>\u4f46\u662fdp[i]\u8fd9\u4e2a\u96c6\u5408\u7684\u5927\u5c0f\u53ef\u80fd\u8fbe\u5230sum^2\uff0c\u6240\u4ee5\u8fd8\u662f\u4f1a\u8d85\u65f6&#8230;<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6 O(n*sum^2)<\/p>\n<p>\u7a7a\u95f4\u590d\u6742\u5ea6\u00a0O(n*sum^2) \u53ef\u964d\u7ef4\u81f3 O(sum^2)<\/p>\n<p>\u9769\u547d\u5c1a\u672a\u6210\u529f\uff0c\u540c\u5fd7\u4ecd\u9700\u52aa\u529b!<\/p>\n<p>all pairs\u7684cost\u592a\u5927\uff0c\u6211\u4eec\u8fd8\u9700\u8981\u7ee7\u7eed\u538b\u7f29\u72b6\u6001\uff01<\/p>\n<p><strong>\u91cd\u70b9\u6765\u4e86<\/strong><\/p>\n<p>\u901a\u8fc7\u89c2\u5bdf\u53d1\u73b0\uff0c\u82e5\u67092\u4e2apairs\uff1a<\/p>\n<p>(h1, h2), (h3, h4),<\/p>\n<p>h1 &lt;= h2, h3 &lt;= h4, h1 &lt; h3, h2 &#8211; h1 = h4 &#8211; h3 \u5373\u00a0<strong>\u9ad8\u5ea6\u5dee<\/strong>\u00a0\u76f8\u540c<\/p>\n<p>\u5982\u679c min(h1, h2) &lt; min(h3, h4) \u90a3\u4e48(h1, h2) \u4e0d\u53ef\u80fd\u4ea7\u751f\u6700\u4f18\u89e3\uff0c\u76f4\u63a5\u820d\u5f03\u3002<\/p>\n<p>\u56e0\u4e3a\u5982\u679c\u540e\u9762\u7684\u67f1\u5b50\u53ef\u4ee5\u6784\u6210 h4 &#8211; h3\/h2 &#8211; h1 \u586b\u8865\u9ad8\u5ea6\u5dee\uff0c\u4f7f\u5f97\u4e24\u6839\u67f1\u5b50\u4e00\u6837\u9ad8\uff0c\u90a3\u4e48\u7b54\u6848\u5c31\u662f h2 \u548c h4\u3002\u4f46h2 &lt; h4\uff0c\u6240\u4ee5\u6700\u4f18\u89e3\u53ea\u80fd\u6765\u81ea\u540e\u8005\u3002<\/p>\n<p>\u4e3e\u4e2a\u4f8b\u5b50\uff1a\u6211\u6709 (1, 3) \u548c (2, 4) \u4e24\u4e2apairs\uff0c\u5b83\u4eec\u7684\u9ad8\u5ea6\u5dee\u90fd\u662f2\uff0c\u5047\u8bbe\u6211\u8fd8\u6709\u4e00\u4e2a\u957f\u5ea6\u4e3a2\u7684\u67f1\u5b50\uff0c\u90a3\u4e48\u6211\u53ef\u4ee5\u6784\u6210(1+2, 3) \u4ee5\u53ca (2+2, 4)\uff0c\u867d\u7136\u8fd9\u4e24\u4e2a\u90fd\u662f\u89e3\u3002\u4f46\u662f\u540e\u8005\u7684\u9ad8\u5ea6\u8981\u5927\u4e8e\u524d\u8005\uff0c\u6240\u4ee5\u524d\u8005\u65e0\u6cd5\u6784\u6210\u6700\u4f18\u89e3\uff0c\u4e5f\u5c31\u6ca1\u5fc5\u8981\u5b58\u4e0b\u6765\u3002<\/p>\n<p>\u6240\u4ee5\uff0c\u6211\u4eec\u53ef\u4ee5\u628a<strong>\u72b6\u6001\u538b\u7f29\u5230\u9ad8\u5ea6\u5dee<\/strong>\uff0c<strong>\u5bf9\u4e8e\u76f8\u540c\u7684\u9ad8\u5ea6\u5dee\uff0c\u6211\u53ea\u5b58h1\u6700\u5927\u7684<\/strong>\u3002<\/p>\n<p>\u6211\u4eec\u7528 dp[i][j] \u6765\u8868\u793a\u4f7f\u7528\u524di\u4e2a\u67f1\u5b50\uff0c\u9ad8\u5ea6\u5dee\u4e3aj\u7684\u60c5\u51b5\u4e0b\u6700\u5927\u7684\u516c\u5171\u9ad8\u5ea6h1\u662f\u591a\u5c11\u3002<\/p>\n<p>\u72b6\u6001\u8f6c\u79fb\uff08\u5982\u4e0b\u56fe\uff09<\/p>\n<p>dp[i][j] = max(dp[i][j], dp[i &#8211; 1][j])<\/p>\n<p>dp[i][j+h] =\u00a0max(dp[i][j + h], dp[i &#8211; 1][j])<\/p>\n<p>dp[i][|j-h|] = max(dp[i][|j-h|], dp[i &#8211; 1][j] + min(j, h))<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6 O(nsum)<\/p>\n<p>\u7a7a\u95f4\u590d\u6742\u5ea6 O(nsum) \u53ef\u964d\u7ef4\u81f3 O(sum)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4428\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4432\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/956-ep234-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p>dp[i] := max common height of two piles of height difference i.<\/p>\n<p>e.g. y1 = 5, y2 = 9 =&gt; dp[9 &#8211; 5] = min(5, 9) =&gt; dp[4] = 5.<\/p>\n<p>answer: dp[0]<\/p>\n<p>Time complexity: O(n*Sum)<\/p>\n<p>Space complexity: O(Sum)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ hashmap<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua, 172 ms\r\nclass Solution {\r\npublic:\r\n  int tallestBillboard(vector&lt;int&gt;&amp; rods) {\r\n    unordered_map&lt;int, int&gt; dp;\r\n    dp[0] = 0;\r\n    for (int rod : rods) {      \r\n      auto cur = dp;\r\n      for (const auto&amp; kv : cur) {\r\n        const int k = kv.first;\r\n        dp[k + rod] = max(dp[k + rod], cur[k]);\r\n        dp[abs(k - rod)] = max(dp[abs(k - rod)], cur[k] + min(rod, k));\r\n      }    \r\n    }\r\n    return dp[0];\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ \/ array<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua, 8 ms\r\nclass Solution {\r\npublic:\r\n  int tallestBillboard(vector&lt;int&gt;&amp; rods) {    \r\n    const int s = accumulate(begin(rods), end(rods), 0);\r\n    vector&lt;int&gt; dp(s + 1, -1);    \r\n    dp[0] = 0;\r\n    for (int rod : rods) {    \r\n      vector&lt;int&gt; cur(dp);\r\n      for (int i = 0; i &lt;= s - rod; ++i) {\r\n        if (cur[i] &lt; 0) continue;\r\n        dp[i + rod] = max(dp[i + rod], cur[i]);\r\n        dp[abs(i - rod)] = max(dp[abs(i - rod)], cur[i] + min(rod, i));\r\n      }    \r\n    }\r\n    return dp[0];\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/2D array<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua, 12 ms\r\nclass Solution {\r\npublic:\r\n  int tallestBillboard(vector&lt;int&gt;&amp; rods) {    \r\n    const int n = rods.size();\r\n    const int s = accumulate(begin(rods), end(rods), 0);\r\n    \/\/ dp[i][j] := min(h1, h2), j = abs(h1 - h2)\r\n    vector&lt;vector&lt;int&gt;&gt; dp(n + 1, vector&lt;int&gt;(s + 1, -1));\r\n    dp[0][0] = 0;\r\n    for (int i = 1; i &lt;= n; ++i) {      \r\n      int h = rods[i - 1];\r\n      for (int j = 0; j &lt;= s - h; ++j) {\r\n        if (dp[i - 1][j] &lt; 0) continue;\r\n        \/\/ not used\r\n        dp[i][j] = max(dp[i][j], dp[i - 1][j]);  \r\n        \/\/ put on the taller one \r\n        dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j]); \r\n        \/\/ put on the shorter one\r\n        dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(h, j)); \r\n      }    \r\n    }\r\n    return dp[n][0];\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem You are installing a billboard and want it to have the largest height.\u00a0 The billboard will have two steel supports, one on each side.\u00a0&#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":[442,18,217,148],"class_list":["post-4423","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-difference","tag-dp","tag-hard","tag-pair","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4423","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=4423"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4423\/revisions"}],"predecessor-version":[{"id":4435,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4423\/revisions\/4435"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4423"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4423"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}