{"id":7808,"date":"2020-12-13T14:25:07","date_gmt":"2020-12-13T22:25:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7808"},"modified":"2020-12-14T17:58:39","modified_gmt":"2020-12-15T01:58:39","slug":"leetcode-1690-stone-game-vii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1690-stone-game-vii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1690. Stone Game VII"},"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 1690. Stone Game VII - \u5237\u9898\u627e\u5de5\u4f5c EP375\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/RVWDJye4kJA?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>Alice and Bob take turns playing a game, with&nbsp;<strong>Alice starting first<\/strong>.<\/p>\n\n\n\n<p>There are&nbsp;<code>n<\/code>&nbsp;stones arranged in a row. On each player&#8217;s turn, they can&nbsp;<strong>remove<\/strong>&nbsp;either the leftmost stone or the rightmost stone from the row and receive points equal to the&nbsp;<strong>sum<\/strong>&nbsp;of the remaining stones&#8217; values in the row. The winner is the one with the higher score when there are no stones left to remove.<\/p>\n\n\n\n<p>Bob found that he will always lose this game (poor Bob, he always loses), so he decided to&nbsp;<strong>minimize the score&#8217;s difference<\/strong>. Alice&#8217;s goal is to&nbsp;<strong>maximize the difference<\/strong>&nbsp;in the score.<\/p>\n\n\n\n<p>Given an array of integers&nbsp;<code>stones<\/code>&nbsp;where&nbsp;<code>stones[i]<\/code>&nbsp;represents the value of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;stone&nbsp;<strong>from the left<\/strong>, return&nbsp;<em>the&nbsp;<strong>difference<\/strong>&nbsp;in Alice and Bob&#8217;s score if they both play&nbsp;<strong>optimally<\/strong>.<\/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> stones = [5,3,1,4,2]\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> \n- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].\n- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].\n- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].\n- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].\n- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].\nThe score difference is 18 - 12 = 6.\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> stones = [7,90,5,1,100,10,10,2]\n<strong>Output:<\/strong> 122<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == stones.length<\/code><\/li><li><code>2 &lt;= n &lt;= 1000<\/code><\/li><li><code>1 &lt;= stones[i] &lt;= 1000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: MinMax + DP<\/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\/12\/1690-ep375.png\" alt=\"\" class=\"wp-image-7817\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1690-ep375.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1690-ep375-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1690-ep375-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>For a sub game of stones[l~r] game(l, r), we have two choices:<br>Remove the left one: sum(stones[l + 1 ~ r]) &#8211; game(l + 1, r)<br>Remove the right one: sum(stones[l ~ r &#8211; 1]) &#8211; game(l, r &#8211; 1)<br>And take the best choice.<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++\/Top Down<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int stoneGameVII(vector<int>& A) {\n    const int n = A.size();\n    vector<vector<int>> cache(n, vector<int>(n, INT_MAX));\n    function<int(int, int, int)> dp = [&](int l, int r, int s) {\n      if (l >= r) return 0;\n      if (cache[l][r] == INT_MAX)\n        cache[l][r] = max(s - A[r] - dp(l, r - 1, s - A[r]),\n                          s - A[l] - dp(l + 1, r, s - A[l]));\n      return cache[l][r];\n    };\n    return dp(0, n - 1, accumulate(begin(A), end(A), 0));\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/Bottom-Up<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int stoneGameVII(vector<int>& A) {\n    const int n = A.size();\n    vector<int> s(n + 1);\n    for (int i = 0; i < n; ++i) s[i + 1] = s[i] + A[i];\n    vector<vector<int>> dp(n, vector<int>(n, 0));\n    for (int c = 2; c <= n; ++c)\n      for (int l = 0, r = l + c - 1; r < n; ++l, ++r)\n        dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r],\n                       s[r] - s[l] - dp[l][r - 1]);\n    return dp[0][n - 1];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def stoneGameVII(self, stones: List[int]) -> int:\n    n = len(stones)\n    s = [0] * (n + 1)\n    for i in range(n): s[i + 1] = s[i] + stones[i]\n    dp = [[0] * n for _ in range(n)]\n    for c in range(2, n + 1):\n      for l in range(0, n - c + 1):\n        r = l + c - 1\n        dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r],\n                       s[r] - s[l] - dp[l][r - 1])\n    return dp[0][n - 1]\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-877-stone-game\/\">https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-877-stone-game\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-1140-stone-game-ii\/\">https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-1140-stone-game-ii\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/game-theory\/leetcode-1406-stone-game-iii\/\">https:\/\/zxi.mytechroad.com\/blog\/game-theory\/leetcode-1406-stone-game-iii\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/game-theory\/leetcode-1510-stone-game-iv\/\">https:\/\/zxi.mytechroad.com\/blog\/game-theory\/leetcode-1510-stone-game-iv\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1563-stone-game-v\/\">https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1563-stone-game-v\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1686-stone-game-vi\/\">https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1686-stone-game-vi\/<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Alice and Bob take turns playing a game, with&nbsp;Alice starting first. There are&nbsp;n&nbsp;stones arranged in a row. On each player&#8217;s turn, they can&nbsp;remove&nbsp;either the leftmost&#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,177,579],"class_list":["post-7808","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-game","tag-medium","tag-minmax","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7808","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=7808"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7808\/revisions"}],"predecessor-version":[{"id":7818,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7808\/revisions\/7818"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7808"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7808"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7808"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}