{"id":7709,"date":"2020-11-22T22:27:48","date_gmt":"2020-11-23T06:27:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7709"},"modified":"2020-11-24T20:13:12","modified_gmt":"2020-11-25T04:13:12","slug":"leetcode-1659-maximize-grid-happiness","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1659-maximize-grid-happiness\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1659. Maximize Grid Happiness"},"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 1659. Maximize Grid Happiness - \u5237\u9898\u627e\u5de5\u4f5c EP371\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/QC0A4L-xkYc?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>You are given four integers,&nbsp;<code>m<\/code>,&nbsp;<code>n<\/code>,&nbsp;<code>introvertsCount<\/code>, and&nbsp;<code>extrovertsCount<\/code>. You have an&nbsp;<code>m x n<\/code>&nbsp;grid, and there are two types of people: introverts and extroverts. There are&nbsp;<code>introvertsCount<\/code>&nbsp;introverts and&nbsp;<code>extrovertsCount<\/code>&nbsp;extroverts.<\/p>\n\n\n\n<p>You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you&nbsp;<strong>do not<\/strong>&nbsp;have to have all the people living in the grid.<\/p>\n\n\n\n<p>The&nbsp;<strong>happiness<\/strong>&nbsp;of each person is calculated as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Introverts&nbsp;<strong>start<\/strong>&nbsp;with&nbsp;<code>120<\/code>&nbsp;happiness and&nbsp;<strong>lose<\/strong>&nbsp;<code>30<\/code>&nbsp;happiness for each neighbor (introvert or extrovert).<\/li><li>Extroverts&nbsp;<strong>start<\/strong>&nbsp;with&nbsp;<code>40<\/code>&nbsp;happiness and&nbsp;<strong>gain<\/strong>&nbsp;<code>20<\/code>&nbsp;happiness for each neighbor (introvert or extrovert).<\/li><\/ul>\n\n\n\n<p>Neighbors live in the directly adjacent cells north, east, south, and west of a person&#8217;s cell.<\/p>\n\n\n\n<p>The&nbsp;<strong>grid happiness<\/strong>&nbsp;is the&nbsp;<strong>sum<\/strong>&nbsp;of each person&#8217;s happiness. Return<em>&nbsp;the&nbsp;<strong>maximum possible grid happiness<\/strong>.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/11\/05\/grid_happiness.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2\n<strong>Output:<\/strong> 240\n<strong>Explanation:<\/strong> Assume the grid is 1-indexed with coordinates (row, column).\nWe can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).\n- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120\n- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60\n- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60\nThe grid happiness is 120 + 60 + 60 = 240.\nThe above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.\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> m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1\n<strong>Output:<\/strong> 260\n<strong>Explanation:<\/strong> Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).\n- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90\n- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80\n- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90\nThe grid happiness is 90 + 80 + 90 = 260.\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> m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0\n<strong>Output:<\/strong> 240\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= m, n &lt;= 5<\/code><\/li><li><code>0 &lt;= introvertsCount, extrovertsCount &lt;= min(m * n, 6)<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: 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\/11\/1659-ep371-1.png\" alt=\"\" class=\"wp-image-7712\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-1-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\/11\/1659-ep371-2.png\" alt=\"\" class=\"wp-image-7713\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-2-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\/11\/1659-ep371-3.png\" alt=\"\" class=\"wp-image-7714\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-3-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\/11\/1659-ep371-4.png\" alt=\"\" class=\"wp-image-7715\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1659-ep371-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp(x, y, in, ex, mask) := max score at (x, y) with in and ex left and the state of previous row is mask.<\/p>\n\n\n\n<p>Mask is ternary, mask(i) = {0, 1, 2} means {empty, in, ex}, there are at most 3^n = 3^5 = 243 different states.<\/p>\n\n\n\n<p>Total states \/ Space complexity: O(m*n*3^n*in*ex) = 5*5*3^5*6*6<br>Space complexity: O(m*n*3^n*in*ex)<\/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 getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {\n    constexpr int kMaxStates = 243;\n    int dp[6][6][7][7][kMaxStates];\n    memset(dp, -1, sizeof(dp));\n    auto get = [](int val, int i) { return val \/ static_cast<int>(pow(3, i)) % 3; };\n    auto update = [](int val, int s) { return (val * 3 + s) % kMaxStates; };\n    vector<int> init{0, 120, 40};\n    vector<int> gain{0, -30, 20};\n    \n    function<int(int,int,int,int,int)> dfs = [&](int x, int y, int in, int ex, int mask) {\n      if (in == 0 && ex == 0) return 0; \/\/ Nothing left.\n      if (x == n) { x = 0; ++y; }\n      if (y == m) return 0; \/\/ Done.\n      int& ans = dp[x][y][in][ex][mask];      \n      if (ans != -1) return ans;\n      \n      ans = dfs(x + 1, y, in, ex, update(mask, 0)); \/\/ Skip current cell.\n      \n      vector<int> counts{0, in, ex};\n      int up = get(mask, n - 1);\n      int left = get(mask, 0);         \n      for (int i = 1; i <= 2; ++i) {\n        if (counts[i] == 0) continue;        \n        int s = init[i];\n        if (y - 1 >= 0 && up) s += gain[i] + gain[up];\n        if (x - 1 >= 0 && left) s += gain[i] + gain[left];\n        ans = max(ans, s + dfs(x + 1, y, in - (i==1), ex - (i==2), update(mask, i)));\n      }\n      return ans;\n    };\n    return dfs(0, 0, introvertsCount, extrovertsCount, 0);\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 getMaxGridHappiness(self, m: int, n: int, I: int, E: int) -> int:    \n    init, gain = [None, 120, 40], [None, -30, 20]\n    \n    get = lambda val, i: (val \/\/ (3 ** i)) % 3\n    update = lambda val, s: (val * 3 + s) % (3 ** n)\n    \n    @lru_cache(None)\n    def dp(x: int, y: int, i: int, e: int, mask: int) -> int:\n      if x == n: x, y = 0, y + 1\n      if i + e == 0 or y == m: return 0\n      \n      ans = dp(x + 1, y, i, e, update(mask, 0))\n      up, left = get(mask, n - 1), get(mask, 0)\n      \n      for cur, count in enumerate([i, e], 1):\n        if count == 0: continue\n        s = init[cur]\n        if x - 1 >= 0 and left: s += gain[cur] + gain[left]\n        if y - 1 >= 0 and up: s += gain[cur] + gain[up]\n        ans = max(ans, s + dp(x + 1, y, \n                              i - (cur == 1), \n                              e - (cur == 2),\n                              update(mask, cur)))\n      return ans\n    return dp(0, 0, I, E, 0)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given four integers,&nbsp;m,&nbsp;n,&nbsp;introvertsCount, and&nbsp;extrovertsCount. You have an&nbsp;m x n&nbsp;grid, and there are two types of people: introverts and extroverts. There are&nbsp;introvertsCount&nbsp;introverts and&nbsp;extrovertsCount&nbsp;extroverts. You&#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,42,589],"class_list":["post-7709","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-search","tag-state-compression","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7709","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=7709"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7709\/revisions"}],"predecessor-version":[{"id":7716,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7709\/revisions\/7716"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7709"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}