{"id":7304,"date":"2020-08-23T11:55:17","date_gmt":"2020-08-23T18:55:17","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7304"},"modified":"2020-08-23T14:49:58","modified_gmt":"2020-08-23T21:49:58","slug":"leetcode-1563-stone-game-v","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1563-stone-game-v\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1563. Stone Game V"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1563. Stone Game V - \u5237\u9898\u627e\u5de5\u4f5c EP352\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/RQSYQGhBDsg?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>There are several stones&nbsp;<strong>arranged in a row<\/strong>, and each stone has an associated&nbsp;value which is an integer given in the array&nbsp;<code>stoneValue<\/code>.<\/p>\n\n\n\n<p>In each round of the game, Alice divides the row into&nbsp;<strong>two non-empty rows<\/strong>&nbsp;(i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and&nbsp;Alice&#8217;s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.<\/p>\n\n\n\n<p>The game ends when there is only&nbsp;<strong>one stone remaining<\/strong>. Alice&#8217;s is initially&nbsp;<strong>zero<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the maximum score that Alice can obtain<\/em>.<\/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> stoneValue = [6,2,3,4,5,5]\n<strong>Output:<\/strong> 18\n<strong>Explanation:<\/strong> In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.\nIn the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).\nThe last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> stoneValue = [7,7,7,7,7,7,7]\n<strong>Output:<\/strong> 28\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> stoneValue = [4]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= stoneValue.length &lt;= 500<\/code><\/li><li><code>1 &lt;=&nbsp;stoneValue[i] &lt;= 10^6<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Range DP + Prefix Sum<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352.png\" alt=\"\" class=\"wp-image-7309\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352-2.png\" alt=\"\" class=\"wp-image-7310\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1563-ep352-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[l][r] := max store Alice can get from range [l, r]<br>sum_l = sum(l, k), sum_r = sum(k + 1, r)<br>dp[l][r] = max{<br>  dp[l][k] + sum_l if sum_l &lt; sum_r<br>  dp[k+1][r] + sum_r if sum_r &lt; sum_l <br>  max(dp[l][k], dp[k+1][r])) + sum_l if sum_l == sum_r)<br>} for k in [l, r)<\/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++\">\nclass Solution {\npublic:\n  int stoneGameV(vector<int>& stoneValue) {\n    const int n = stoneValue.size();\n    vector<int> sums(n + 1);\n    for (int i = 0; i < n; ++i)\n      sums[i + 1] = sums[i] + stoneValue[i];\n    vector<vector<int>> cache(n, vector<int>(n, -1));\n    \/\/ max value alice can get from range [l, r]\n    function<int(int, int)> dp = [&](int l, int r) {\n      if (l == r) return 0;\n      int& ans = cache[l][r];\n      if (ans != -1) return ans;\n      for (int k = l; k < r; ++k) {\n        \/\/ left: [l, k], right: [k + 1, r]\n        int sum_l = sums[k + 1] - sums[l];\n        int sum_r = sums[r + 1] - sums[k + 1];\n        if (sum_l > sum_r)\n          ans = max(ans, sum_r + dp(k + 1, r));\n        else if (sum_l < sum_r)\n          ans = max(ans, sum_l + dp(l, k));\n        else\n          ans = max(ans, sum_l + max(dp(l, k), dp(k + 1, r)));\n      }      \n      return ans;\n    };\n    \n    return dp(0, n - 1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are several stones&nbsp;arranged in a row, and each stone has an associated&nbsp;value which is an integer given in the array&nbsp;stoneValue. In each round 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":[46],"tags":[18,217,200,139],"class_list":["post-7304","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-prefix-sum","tag-range","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7304","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=7304"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7304\/revisions"}],"predecessor-version":[{"id":7311,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7304\/revisions\/7311"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}