{"id":6844,"date":"2020-05-30T18:57:14","date_gmt":"2020-05-31T01:57:14","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6844"},"modified":"2020-05-30T23:34:34","modified_gmt":"2020-05-31T06:34:34","slug":"leetcode-1463-cherry-pickup-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1463-cherry-pickup-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1463. Cherry Pickup 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 1463. Cherry Pickup II - \u5237\u9898\u627e\u5de5\u4f5c EP331\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/Et-7IP5-6wA?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>Given a&nbsp;<code>rows x cols<\/code>&nbsp;matrix&nbsp;<code>grid<\/code>&nbsp;representing a field of cherries.&nbsp;Each cell in&nbsp;<code>grid<\/code>&nbsp;represents the number of cherries that you can collect.<\/p>\n\n\n\n<p>You have two&nbsp;robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.<\/p>\n\n\n\n<p>Return the maximum number of cherries collection using both robots&nbsp; by following the rules below:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).<\/li><li>When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).<\/li><li>When both robots stay on the same cell, only one of them takes the cherries.<\/li><li>Both robots cannot move outside of the grid at&nbsp;any moment.<\/li><li>Both robots should reach the bottom row in the&nbsp;<code>grid<\/code>.<\/li><\/ul>\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\/04\/29\/sample_1_1802.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]\n<strong>Output:<\/strong> 24\n<strong>Explanation:<\/strong>&nbsp;Path of robot #1 and #2 are described in color green and blue respectively.\nCherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.\nCherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.\nTotal of cherries: 12 + 12 = 24.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/04\/23\/sample_2_1802.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]\n<strong>Output:<\/strong> 28\n<strong>Explanation:<\/strong>&nbsp;Path of robot #1 and #2 are described in color green and blue respectively.\nCherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.\nCherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.\nTotal of cherries: 17 + 11 = 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> grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]\n<strong>Output:<\/strong> 22\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,1],[1,1]]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>rows == grid.length<\/code><\/li><li><code>cols == grid[i].length<\/code><\/li><li><code>2 &lt;= rows, cols &lt;= 70<\/code><\/li><li><code>0 &lt;= grid[i][j] &lt;= 100&nbsp;<\/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\/05\/1463-ep331.png\" alt=\"\" class=\"wp-image-6851\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1463-ep331.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1463-ep331-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1463-ep331-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[y][x1][x2] := max cherry when ro1 at (x1, y) and ro2 at (x2, y)<br>dp[y][x1][x2]  = max(dp[y+1][x1 + dx1][x2 + dx2])  -1 &lt;= dx1, dx2 &lt;= 1<\/p>\n\n\n\n<p>Time complexity: O(c^2*r)<br>Space complexity: O(c^2*r)<\/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\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int cherryPickup(vector<vector<int>>& grid) {\n    const int r = grid.size();\n    const int c = grid[0].size();\n    vector<vector<vector<int>>> cache(r, vector<vector<int>>(c, vector<int>(c, -1)));\n    function<int(int, int, int)> dp = [&](int y, int x1, int x2) {\n      if (x1 < 0 || x1 >= c || x2 < 0 || x2 >= c || y < 0 || y >= r) return 0;\n      int& ans = cache[y][x1][x2];\n      if (ans != -1) return ans;\n      const int cur = grid[y][x1] + (x1 != x2) * grid[y][x2];\n      for (int d1 = -1; d1 <= 1; ++d1)\n        for (int d2 = -1; d2 <= 1; ++d2)\n          ans = max(ans, cur + dp(y + 1, x1 + d1, x2 + d2));\n      return ans;\n    };\n    return dp(0, 0, c - 1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><span id=\"qt-caret\"><\/span><\/p>\n\n\n\n<p>Bottom-up<\/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\nclass Solution {\npublic:\n  int cherryPickup(vector<vector<int>>& grid) {\n    const int r = grid.size();\n    const int c = grid[0].size();\n    vector<vector<vector<int>>> dp(r + 2, \n      vector<vector<int>>(c + 2, vector<int>(c + 2)));\n    for (int y = r; y >= 1; --y)\n      for (int x1 = 1; x1 <= c; ++x1)\n        for (int x2 = 1; x2 <= c; ++x2) {\n          const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];\n          int&#038; ans = dp[y][x1][x2];\n          for (int d1 = -1; d1 <= 1; ++d1)\n            for (int d2 = -1; d2 <= 1; ++d2)\n              ans = max(ans, cur + dp[y + 1][x1 + d1][x2 + d2]);          \n        }\n    return dp[1][1][c];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>O(c^2) Space<\/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\nclass Solution {\npublic:\n  int cherryPickup(vector<vector<int>>& grid) {\n    const int r = grid.size();\n    const int c = grid[0].size();\n    vector<vector<int>> dp(c + 2, vector<int>(c + 2));\n    for (int y = r; y >= 1; --y) {\n      vector<vector<int>> tmp(c + 2, vector<int>(c + 2));\n      for (int x1 = 1; x1 <= c; ++x1)\n        for (int x2 = 1; x2 <= c; ++x2) {\n          const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];\n          for (int d1 = -1; d1 <= 1; ++d1)\n            for (int d2 = -1; d2 <= 1; ++d2)\n              tmp[x1][x2] = max(tmp[x1][x2], cur + dp[x1 + d1][x2 + d2]);          \n        }\n      dp.swap(tmp);\n    }\n    return dp[1][c];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;rows x cols&nbsp;matrix&nbsp;grid&nbsp;representing a field of cherries.&nbsp;Each cell in&nbsp;grid&nbsp;represents the number of cherries that you can collect. You have two&nbsp;robots that can collect cherries&#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],"class_list":["post-6844","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6844","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=6844"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6844\/revisions"}],"predecessor-version":[{"id":6853,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6844\/revisions\/6853"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}