{"id":3354,"date":"2018-07-28T21:53:23","date_gmt":"2018-07-29T04:53:23","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3354"},"modified":"2018-07-30T21:28:28","modified_gmt":"2018-07-31T04:28:28","slug":"leetcode-877-stone-game","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-877-stone-game\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 877. Stone Game"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 877 Stone Game - \u5237\u9898\u627e\u5de5\u4f5c EP213\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/xJ1Rc30Pyes?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>Alex and Lee play a game with piles of stones.\u00a0 There are an even number of\u00a0piles\u00a0<strong>arranged in a row<\/strong>, and each pile has a positive integer number of stones\u00a0<code>piles[i]<\/code>.<\/p>\n<p>The objective of the game is to end with the most\u00a0stones.\u00a0 The total number of stones is odd, so there are no ties.<\/p>\n<p>Alex and Lee take turns, with Alex starting first.\u00a0 Each turn, a player\u00a0takes the entire pile of stones from either the beginning or the end of the row.\u00a0 This continues until there are no more piles left, at which point the person with the most stones wins.<\/p>\n<p>Assuming Alex and Lee play optimally, return\u00a0<code>True<\/code>\u00a0if and only if Alex wins the game.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[5,3,4,5]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">true<\/span>\r\n<strong>Explanation: <\/strong>\r\nAlex starts first, and can only take the first 5 or the last 5.\r\nSay he takes the first 5, so that the row becomes [3, 4, 5].\r\nIf Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.\r\nIf Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.\r\nThis demonstrated that taking the first 5 was a winning move for Alex, so we return true.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>2 &lt;= piles.length &lt;= 500<\/code><\/li>\n<li><code>piles.length<\/code>\u00a0is even.<\/li>\n<li><code>1 &lt;= piles[i] &lt;= 500<\/code><\/li>\n<li><code>sum(piles)<\/code>\u00a0is odd.<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3385\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/877-ep213.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/877-ep213.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/877-ep213-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/877-ep213-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution 1: min-max (TLE)<\/strong><\/h1>\n<p>Time complexity: O(2^n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: TLE 26\/46 passed.\r\nclass Solution {\r\npublic:\r\n  bool stoneGame(vector&lt;int&gt;&amp; piles) {\r\n    return score(piles, 0, piles.size() - 1) &gt; 0;\r\n  }\r\nprivate:\r\n  int score(const vector&lt;int&gt;&amp; piles, int l, int r) {\r\n    if (l == r) return piles[l];\r\n    return max(piles[l] - score(piles, l + 1, r),\r\n               piles[r] - score(piles, l, r - 1));\r\n  }\r\n};<\/pre>\n<h1><strong>Solution 2: min-max + memorization<\/strong><\/h1>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n^2)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  bool stoneGame(vector&lt;int&gt;&amp; piles) {\r\n    const int n = piles.size();\r\n    m_ = vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(n, INT_MIN));\r\n    return score(piles, 0, n - 1) &gt; 0;\r\n  }\r\nprivate:\r\n  vector&lt;vector&lt;int&gt;&gt; m_;\r\n  int score(const vector&lt;int&gt;&amp; piles, int l, int r) {\r\n    if (l == r) return piles[l];\r\n    if (m_[l][r] == INT_MIN)\r\n      m_[l][r] = max(piles[l] - score(piles, l + 1, r),\r\n                     piles[r] - score(piles, l, r - 1));\r\n    return m_[l][r];\r\n  }\r\n};<\/pre>\n<h1><strong>Solution 3:\u00a0 min-max + DP<\/strong><\/h1>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n^2)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  bool stoneGame(vector&lt;int&gt;&amp; piles) {\r\n    const int n = piles.size();\r\n    \/\/ dp[i][j] := max(your_stones - op_stones) for piles[i] ~ piles[j]\r\n    vector&lt;vector&lt;int&gt;&gt; dp(n, vector&lt;int&gt;(n, 0));\r\n    for (int i = 0; i &lt; n; ++i)\r\n      dp[i][i] = piles[i];\r\n    for (int l = 2; l &lt;= n; ++l)\r\n      for (int i = 0; i &lt; n - l + 1; ++i) {\r\n        int j = i + l - 1;\r\n        dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);\r\n      }\r\n    return dp[0][n - 1] &gt; 0;    \r\n  }\r\n};<\/pre>\n<p>O(n) Space<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\npublic:\r\n  bool stoneGame(vector&lt;int&gt;&amp; piles) {\r\n    const int n = piles.size();\r\n    \/\/ dp[i] := max(your_stones - op_stones) for piles[i] to piles[i + l - 1]\r\n    vector&lt;int&gt; dp(piles);    \r\n    for (int l = 2; l &lt;= n; ++l)\r\n      for (int i = 0; i &lt; n - l + 1; ++i)       \r\n        dp[i] = max(piles[i] - dp[i + 1], piles[i + l - 1] - dp[i]);\r\n    return dp[0] &gt; 0;\r\n  }\r\n};<\/pre>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-486-predict-the-winner\/\">\u82b1\u82b1\u9171 LeetCode 486. Predict the Winner<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem Alex and Lee play a game with piles of stones.\u00a0 There are an even number of\u00a0piles\u00a0arranged in a row, and each pile has a&#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,27,25],"class_list":["post-3354","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-game","tag-min-max","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3354","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=3354"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3354\/revisions"}],"predecessor-version":[{"id":3391,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3354\/revisions\/3391"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}