{"id":5368,"date":"2019-07-27T22:47:25","date_gmt":"2019-07-28T05:47:25","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5368"},"modified":"2019-07-29T20:41:07","modified_gmt":"2019-07-30T03:41:07","slug":"leetcode-1140-stone-game-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-1140-stone-game-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1140. Stone Game II"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1140. Stone Game II - \u5237\u9898\u627e\u5de5\u4f5c EP260\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/e_FrC5xavwI?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>\n<\/div><\/figure>\n\n\n\n<p>Alex&nbsp;and Lee continue their&nbsp;games with piles of stones.&nbsp; There are a number of&nbsp;piles&nbsp;<strong>arranged in a row<\/strong>, and each pile has a positive integer number of stones&nbsp;<code>piles[i]<\/code>.&nbsp; The objective of the game is to end with the most&nbsp;stones.&nbsp;<\/p>\n\n\n\n<p>Alex and Lee take turns, with Alex starting first.&nbsp; Initially,&nbsp;<code>M = 1<\/code>.<\/p>\n\n\n\n<p>On each player&#8217;s turn, that player&nbsp;can take&nbsp;<strong>all the stones<\/strong>&nbsp;in the&nbsp;<strong>first<\/strong>&nbsp;<code>X<\/code>&nbsp;remaining piles, where&nbsp;<code>1 &lt;= X &lt;= 2M<\/code>.&nbsp; Then, we set&nbsp;<code>M = max(M, X)<\/code>.<\/p>\n\n\n\n<p>The game continues until all the stones have been taken.<\/p>\n\n\n\n<p>Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> piles = [2,7,9,4,4]\n<strong>Output:<\/strong> 10\n<strong>Explanation:<\/strong>  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger. \n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= piles.length &lt;= 100<\/code><\/li><li><code>1 &lt;= piles[i]&nbsp;&lt;= 10 ^ 4<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion + Memoization<\/strong><\/h2>\n\n\n\n<p>def solve(s, m) = max diff score between two players starting from s for the given M.<\/p>\n\n\n\n<p>cache[s][M] = max{sum(piles[s:s+x]) &#8211; solve(s+x, max(x, M)}, 1 &lt;= x &lt;= 2*M, s + x &lt;= n<\/p>\n\n\n\n<p>Time complexity: O(n^3)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 12 ms \/ 9.7 MB\nclass Solution {\npublic:\n  int stoneGameII(vector<int>& piles) {\n    const int n = piles.size();\n    unordered_map<int, int> cache;\n    \/\/ Maximum diff starting from piles[s] given M.\n    function<int(int, int)> solve = [&](int s, int M) {\n      if (s >= n) return 0;\n      const int key = (s << 8) | M;\n      if (cache.count(key)) return cache[key];\n      int best = INT_MIN;\n      int curr = 0;\n      for (int x = 1; x <= 2 * M; ++x) {\n        if (s + x > n) break;\n        curr += piles[s + x - 1];\n        best = max(best, curr - solve(s + x, max(x, M)));\n      }\n      return cache[key] = best;\n    };    \n    int total = accumulate(begin(piles), end(piles), 0);\n    return  (total + solve(0, 1)) \/ 2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Alex&nbsp;and Lee continue their&nbsp;games with piles of stones.&nbsp; There are a number of&nbsp;piles&nbsp;arranged in a row, and each pile has a positive integer number of&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[153],"tags":[18,27,177,17],"class_list":["post-5368","post","type-post","status-publish","format-standard","hentry","category-recursion","tag-dp","tag-game","tag-medium","tag-recursion","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5368","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=5368"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5368\/revisions"}],"predecessor-version":[{"id":5379,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5368\/revisions\/5379"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}