{"id":2062,"date":"2018-03-11T00:11:49","date_gmt":"2018-03-11T08:11:49","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2062"},"modified":"2018-03-15T21:47:48","modified_gmt":"2018-03-16T04:47:48","slug":"leetcode-799-champagne-tower","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-799-champagne-tower\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 799. Champagne Tower"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 799. Champagne Tower - \u5237\u9898\u627e\u5de5\u4f5c EP173\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/OqXzKsEWM44?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>\u9898\u76ee\u5927\u610f\uff1a\u5f80\u4e00\u4e2a\u9999\u69df\u5854\uff08i\u5c42\u6709i\u4e2a\u676f\u5b50\uff09\u5012\u5165n\u4e2a\u676f\u5b50\u5bb9\u91cf\u7684\u9999\u69df\u4e4b\u540e\uff0c\u6c42\u6307\u5b9a\u4f4d\u7f6e\u676f\u5b50\u4e2d\u9152\u7684\u5bb9\u91cf\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/champagne-tower\/description\/\">https:\/\/leetcode.com\/problems\/champagne-tower\/description\/<\/a><\/p>\n<p>We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row.\u00a0 Each glass holds one cup (250ml) of champagne.<\/p>\n<p>Then, some champagne is poured in the first glass at the top.\u00a0 When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it.\u00a0 When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on.\u00a0 (A glass at the bottom row has it&#8217;s excess champagne fall on the floor.)<\/p>\n<p>For example, after one cup of champagne is poured, the top most glass is full.\u00a0 After two cups of champagne are poured, the two glasses on the second row are half full.\u00a0 After three cups of champagne are poured, those two cups become full &#8211; there are 3 full glasses total now.\u00a0 After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/03\/09\/tower.png\" alt=\"\" \/><\/p>\n<p>Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"\">Example 1:\r\nInput: poured = 1, query_glass = 1, query_row = 1\r\nOutput: 0.0\r\nExplanation: We poured 1 cup of champagne to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.\r\n\r\nExample 2:\r\nInput: poured = 2, query_glass = 1, query_row = 1\r\nOutput: 0.5\r\nExplanation: We poured 2 cups of champagne to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>poured<\/code>\u00a0will\u00a0be\u00a0in the range of\u00a0<code>[0, 10 ^ 9]<\/code>.<\/li>\n<li><code>query_glass<\/code>\u00a0and\u00a0<code>query_row<\/code>\u00a0will be in the range of\u00a0<code>[0, 99]<\/code>.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2074\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/> <img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2075\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/799-ep173-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><strong>Idea: DP + simulation<\/strong><\/p>\n<p>define dp[i][j] as the volume of\u00a0champagne will be\u00a0<span style=\"color: #ff0000;\"><strong>poured into<\/strong><\/span> the j -th glass in the i-th row, dp[i][j] can be greater than 1.<\/p>\n<p>Init dp[0][0] = poured.<\/p>\n<p>Transition: if dp[i][j] &gt; 1, it will overflow, the overflow part will be evenly distributed to dp[i+1][j], dp[i+1][j+1]<\/p>\n<p>if dp[i][j] &gt; 1:<br \/>\ndp[i+1][j] += (dp[i][j] &#8211; 1) \/ 2.0<br \/>\ndp[i+1][j + 1] += (dp[i][j] &#8211; 1) \/ 2.0<\/p>\n<p>Answer: min(1.0, dp[query_row][query_index])<\/p>\n<p><strong>Solution 1:<\/strong><\/p>\n<p>C++<\/p>\n<p>Time complexity: O(100*100)<\/p>\n<p>Space complexity: O(100*100)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 22 ms\r\nclass Solution {\r\npublic:\r\n  double champagneTower(int poured, int query_row, int query_glass) {\r\n    constexpr int kRows = 100;\r\n    vector&lt;vector&lt;double&gt;&gt; dp(kRows, vector&lt;double&gt;(kRows));\r\n    dp[0][0] = poured;\r\n    for (int i = 0; i &lt; kRows - 1; ++i)\r\n      for (int j = 0; j &lt;= i; ++j)\r\n        if (dp[i][j] &gt; 1) {\r\n          dp[i + 1][j    ] += (dp[i][j] - 1) \/ 2.0;\r\n          dp[i + 1][j + 1] += (dp[i][j] - 1) \/ 2.0;\r\n          dp[i][j] = 1.0;\r\n        }\r\n    return std::min(1.0, dp[query_row][query_glass]);\r\n  }\r\n};<\/pre>\n<p>Pull<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 27 ms\r\nclass Solution {\r\npublic:\r\n  double champagneTower(int poured, int query_row, int query_glass) {\r\n    constexpr int kRows = 100;\r\n    vector&lt;vector&lt;double&gt;&gt; dp(kRows, vector&lt;double&gt;(kRows));\r\n    dp[0][0] = poured;\r\n    for (int i = 1; i &lt; kRows; ++i)\r\n      for (int j = 0; j &lt;= i; ++j) {\r\n        if (j &gt; 0) dp[i][j] += max(0.0, (dp[i - 1][j - 1] - 1) \/ 2.0);\r\n        if (j &lt; i) dp[i][j] += max(0.0, (dp[i - 1][j    ] - 1) \/ 2.0);\r\n      } \r\n    return std::min(1.0, dp[query_row][query_glass]);\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++<\/p>\n<p>Time complexity: O(rows * 100)<\/p>\n<p>Space complexity: O(100)<\/p>\n<p>Push<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\npublic:\r\n  double champagneTower(int poured, int query_row, int query_glass) {\r\n    constexpr int kCols = 100;\r\n    vector&lt;double&gt; dp(kCols);\r\n    dp[0] = poured;\r\n    for (int i = 0; i &lt; query_row; ++i) {\r\n      vector&lt;double&gt; tmp(kCols);\r\n      for (int j = 0; j &lt;= i; ++j)\r\n        if (dp[j] &gt; 1) {\r\n          tmp[j    ] += (dp[j] - 1) \/ 2.0;\r\n          tmp[j + 1] += (dp[j] - 1) \/ 2.0;          \r\n        }\r\n      dp.swap(tmp);\r\n    }\r\n    return std::min(1.0, dp[query_glass]);\r\n  }\r\n};<\/pre>\n<p>Pull<\/p>\n<pre class=\"lang:c++ decode:true\">class Solution {\r\npublic:\r\n  double champagneTower(int poured, int query_row, int query_glass) {    \r\n    constexpr int kCols = 100;\r\n    vector&lt;double&gt; dp(kCols);\r\n    dp[0] = poured;\r\n    for (int i = 1; i &lt;= query_row; ++i) {\r\n      vector&lt;double&gt; tmp(kCols);\r\n      for (int j = 0; j &lt;= i; ++j) {\r\n        if (j &gt; 0) tmp[j] += max(0.0, (dp[j - 1] - 1) \/ 2.0); \r\n        if (j &lt; i) tmp[j] += max(0.0, (dp[j    ] - 1) \/ 2.0);        \r\n      }\r\n      dp.swap(tmp);\r\n    }\r\n    return std::min(1.0, dp[query_glass]);\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u5f80\u4e00\u4e2a\u9999\u69df\u5854\uff08i\u5c42\u6709i\u4e2a\u676f\u5b50\uff09\u5012\u5165n\u4e2a\u676f\u5b50\u5bb9\u91cf\u7684\u9999\u69df\u4e4b\u540e\uff0c\u6c42\u6307\u5b9a\u4f4d\u7f6e\u676f\u5b50\u4e2d\u9152\u7684\u5bb9\u91cf\u3002 Problem: https:\/\/leetcode.com\/problems\/champagne-tower\/description\/ We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on&#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,48],"tags":[18,177,179],"class_list":["post-2062","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-simulation","tag-dp","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2062","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=2062"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2062\/revisions"}],"predecessor-version":[{"id":2077,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2062\/revisions\/2077"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2062"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2062"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2062"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}