{"id":1098,"date":"2017-12-04T16:47:48","date_gmt":"2017-12-05T00:47:48","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1098"},"modified":"2018-09-18T08:40:48","modified_gmt":"2018-09-18T15:40:48","slug":"leetcode-741-cherry-pickup","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-741-cherry-pickup\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 741. Cherry Pickup"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode  741. Cherry Pickup - \u5237\u9898\u627e\u5de5\u4f5c EP123\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/vvPSWORCKow?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><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u6a31\u6843\u7530\u7684\u5730\u56fe\uff081: \u6a31\u6843, 0: \u7a7a, -1: \u969c\u788d\u7269\uff09\u3002\u7136\u4f60\u4ece\u5de6\u4e0a\u89d2\u8d70\u5230\u53f3\u4e0b\u89d2\uff08\u53ea\u80fd\u5f80\u53f3\u6216\u5f80\u4e0b\uff09\uff0c\u518d\u4ece\u53f3\u4e0b\u89d2\u8d70\u56de\u5de6\u4e0a\u89d2\uff08\u53ea\u80fd\u5f80\u5de6\u6216\u8005\u5f80\u4e0a\uff09\u3002\u95ee\u4f60\u6700\u591a\u80fd\u91c7\u5230\u591a\u5c11\u68f5\u6a31\u6843\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>In a N x N\u00a0<code>grid<\/code>\u00a0representing a field of cherries, each cell is one of three possible integers.<\/p>\n<ul>\n<li>0 means the cell is empty, so you can pass through;<\/li>\n<li>1 means the cell contains a cherry, that you can pick up and pass through;<\/li>\n<li>-1 means the cell contains a thorn that blocks your way.<\/li>\n<\/ul>\n<p>Your task is to collect maximum number of cherries possible by following the rules below:<\/p>\n<ul>\n<li>Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1);<\/li>\n<li>After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells;<\/li>\n<li>When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0);<\/li>\n<li>If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.<\/li>\n<\/ul>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"theme:github lang:default highlight:0 decode:true\">Input: grid =\r\n[[0, 1, -1],\r\n [1, 0, -1],\r\n [1, 1,  1]]\r\nOutput: 5\r\nExplanation: \r\nThe player started at (0, 0) and went down, down, right right to reach (2, 2).\r\n4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].\r\nThen, the player went left, up, up, left to return home, picking up one more cherry.\r\nThe total number of cherries picked up is 5, and this is the maximum possible.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li><code>grid<\/code>\u00a0is an\u00a0<code>N<\/code>\u00a0by\u00a0<code>N<\/code>\u00a02D array, with\u00a0<code>1 &lt;= N &lt;= 50<\/code>.<\/li>\n<li>Each\u00a0<code>grid[i][j]<\/code>\u00a0is an integer in the set\u00a0<code>{-1, 0, 1}<\/code>.<\/li>\n<li>It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.<\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea<\/strong>:<\/p>\n<p>DP<\/p>\n<p><span style=\"font-weight: 400;\">Key observation: (0,0) to (n-1, n-1) to (0, 0) is the same as (n-1,n-1) to (0,0) twice<\/span><\/p>\n<ol>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Two people starting from (n-1, n-1) and go to (0, 0). <\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">They move one step (left or up) at a time simultaneously. And pick up the cherry within the grid (if there is one).<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">if they ended up at the same grid with a cherry. Only one of them can pick up it.<\/span><\/li>\n<\/ol>\n<p><span style=\"font-weight: 400;\">Solution: DP \/ Recursion with memoization. <\/span><\/p>\n<p><span style=\"font-weight: 400;\">x1, y1, x2 to represent a state y2 can be computed: y2 = x1 + y1 &#8211; x2<\/span><\/p>\n<p><span style=\"font-weight: 400;\">dp(x1, y1, x2) computes the max cherries if start from {(x1, y1), (x2, y2)} to (0, 0), which is a recursive function.<\/span><\/p>\n<p>Since two people move independently, there are 4 subproblems: (left, left), (left, up), (up, left), (left, up). Finally, we have:<\/p>\n<p><span style=\"font-weight: 400;\">dp(x1, y1, x2)= g[y1][x1] + g[y2][x2] + max{dp(x1-1,y1,x2-1), <\/span><span style=\"font-weight: 400;\">dp(x1,y1-1,x2-1), dp(x1-1,y1,x2), dp(x1,y1-1,x2)<\/span><span style=\"font-weight: 400;\">}<\/span><\/p>\n<p><span style=\"font-weight: 400;\">Time complexity: O(n^<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\">) <\/span><\/p>\n<p><span style=\"font-weight: 400;\">Space complexity: O(n^<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\">)<\/span><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/741-ep123.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1102\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/741-ep123.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/741-ep123.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/741-ep123-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/741-ep123-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>Time complexity: O(n^3)<\/p>\n<p>Space complexity: O(n^3)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C ++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 32 ms\r\nclass Solution {\r\npublic:\r\n    int cherryPickup(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {\r\n        const int n = grid.size();\r\n        grid_ = &amp;grid;\r\n        m_ = vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;(\r\n                n, vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(n, INT_MIN)));\r\n        return max(0, dp(n - 1, n - 1, n - 1));\r\n    }\r\nprivate:\r\n    \/\/ max cherries from (x1, y1) to (0, 0) + (x2, y2) to (0, 0)\r\n    int dp(int x1, int y1, int x2) {\r\n        const int y2 = x1 + y1 - x2;\r\n        if (x1 &lt; 0 || y1 &lt; 0 || x2 &lt; 0 || y2 &lt; 0) return -1;\r\n        if ((*grid_)[y1][x1] &lt; 0 || (*grid_)[y2][x2] &lt; 0) return -1;\r\n        if (x1 == 0 &amp;&amp; y1 == 0) return (*grid_)[y1][x1];\r\n        if (m_[x1][y1][x2] != INT_MIN) return m_[x1][y1][x2];        \r\n        int ans =  max(max(dp(x1 - 1, y1, x2 - 1), dp(x1, y1 - 1, x2)),\r\n                       max(dp(x1, y1 - 1, x2 - 1), dp(x1 - 1, y1, x2)));\r\n        if (ans &lt; 0) return m_[x1][y1][x2] = -1;\r\n        ans += (*grid_)[y1][x1];\r\n        if (x1 != x2) ans += (*grid_)[y2][x2];\r\n        \r\n        return m_[x1][y1][x2] = ans;\r\n    }\r\n    \r\n    vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt; m_;\r\n    vector&lt;vector&lt;int&gt;&gt;* grid_; \/\/ does not own the object\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\nclass Solution {\r\n  private int[][] grid;\r\n  private int[][][] memo;  \r\n  public int cherryPickup(int[][] grid) {\r\n    this.grid = grid;\r\n    int m = grid.length;\r\n    int n = grid[0].length;\r\n    memo = new int[m][n][n];\r\n    for (int i = 0; i &lt; m; ++i)\r\n      for (int j = 0; j &lt; n; ++j)\r\n        Arrays.fill(memo[i][j], Integer.MIN_VALUE);\r\n    return Math.max(0, dp(n - 1, m - 1, n - 1));\r\n  }\r\n  \r\n  private int dp(int x1, int y1, int x2) {\r\n    final int y2 = x1 + y1 - x2;\r\n    if (x1 &lt; 0 || y1 &lt; 0 || x2 &lt; 0 || y2 &lt; 0) return -1;\r\n    if (grid[y1][x1] &lt; 0 || grid[y2][x2] &lt; 0) return -1;\r\n    if (x1 == 0 &amp;&amp; y1 == 0) return grid[y1][x1];\r\n    if (memo[y1][x1][x2] != Integer.MIN_VALUE) return memo[y1][x1][x2];\r\n    memo[y1][x1][x2] = Math.max(Math.max(dp(x1 - 1, y1, x2 - 1), dp(x1, y1 - 1, x2)),\r\n                                Math.max(dp(x1, y1 - 1, x2 - 1), dp(x1 - 1, y1, x2)));\r\n    \r\n    if (memo[y1][x1][x2] &gt;= 0) {\r\n      memo[y1][x1][x2] += grid[y1][x1];\r\n      if (x1 != x2) memo[y1][x1][x2] += grid[y2][x2];\r\n    }\r\n    \r\n    return memo[y1][x1][x2];\r\n  }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<\/div><\/div>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-64-minimum-path-sum\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 64. Minimum Path Sum<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-63-unique-paths-ii\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 63. Unique Paths II<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-62-unique-paths\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 62. Unique Paths<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u6a31\u6843\u7530\u7684\u5730\u56fe\uff081: \u6a31\u6843, 0: \u7a7a, -1: \u969c\u788d\u7269\uff09\u3002\u7136\u4f60\u4ece\u5de6\u4e0a\u89d2\u8d70\u5230\u53f3\u4e0b\u89d2\uff08\u53ea\u80fd\u5f80\u53f3\u6216\u5f80\u4e0b\uff09\uff0c\u518d\u4ece\u53f3\u4e0b\u89d2\u8d70\u56de\u5de6\u4e0a\u89d2\uff08\u53ea\u80fd\u5f80\u5de6\u6216\u8005\u5f80\u4e0a\uff09\u3002\u95ee\u4f60\u6700\u591a\u80fd\u91c7\u5230\u591a\u5c11\u68f5\u6a31\u6843\u3002 Problem: In a N x N\u00a0grid\u00a0representing a field of cherries, each cell is one of three possible integers. 0&#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,132],"class_list":["post-1098","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-path-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1098","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=1098"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1098\/revisions"}],"predecessor-version":[{"id":4029,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1098\/revisions\/4029"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1098"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1098"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1098"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}