{"id":1146,"date":"2023-12-20T13:00:00","date_gmt":"2023-12-20T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1146"},"modified":"2023-12-26T10:31:44","modified_gmt":"2023-12-26T10:31:44","slug":"cherry-pickup","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/cherry-pickup\/","title":{"rendered":"Cherry Pickup Problem Solved (C++, Java, Python)"},"content":{"rendered":"\n<p>The Dynamic programming method is used in problems where we have to explore all the possibilities and the <strong>cherry pickup<\/strong> problem is one of them in which we have to explore all the feasible paths for picking maximum cherries. In this article, we will explore approaches to solve this Cherry Pickup problem from leetcode and how to implement them.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Cherry Pickup Problem?<\/strong><\/h2>\n\n\n\n<p><strong>In the Cherry Pickup problem, we are given a grid that represents a field of cherries, each cell is one of these three possible integers: 0, 1, -1. Among these, an empty cell is represented by 0, a cell that contains cherry is represented by 1, and a cell that thorns is represented by -1.<\/strong><\/p>\n\n\n\n<p>We have to collect the maximum number of cherries from the fields by following the rules below:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We have to start from (0,0) and reach (n-1,n-1) by moving right and down through valid path cells.<\/li>\n\n\n\n<li>After reaching (n &#8211; 1, n &#8211; 1) we have to return to (0, 0) by moving left or up through valid path cells.<\/li>\n\n\n\n<li>When we pick a cherry from a valid cell that cell becomes an empty cell.<\/li>\n<\/ul>\n\n\n\n<p>Let&#8217;s take an example to solve this problem.<\/p>\n\n\n\n<p>Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]<\/p>\n\n\n\n<p>Output: 5<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"422\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12-1024x422.png\" alt=\"Example of Cherry Pickup Problem\" class=\"wp-image-1149\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12-1024x422.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12-300x124.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12-768x316.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12-750x309.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12-1140x469.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-12.png 1275w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>Let\u2019s solve it using a dynamic programming approach.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Dynamic Programming Approach<\/strong><\/h2>\n\n\n\n<p>If we want to solve it using <a href=\"https:\/\/favtutor.com\/blogs\/dynamic-programming\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/dynamic-programming\">dynamic programming<\/a>, we have to take the cherries in such a way that it takes a maximum of it, reaching (n-1,n-1) from (0,0), if possible and we have to make one traversal from (n-1, n-1) to (0, 0) such that it can take the maximum of the remaining cherries.&nbsp;<\/p>\n\n\n\n<p>For this, we can think in a way that two people are collecting cherries, and they are following these steps:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>In a two-person strategy, we will visualize the two persons simultaneously traversing the grid, each starting from the origin (0, 0) and moving toward the destination (n-1, n-1).<\/li>\n\n\n\n<li>we can say that distance of person1 from origin is equal to distance of person2 from origin i.e r1+c1=r2+c2<\/li>\n\n\n\n<li>At each cell, consider the cherry at the current position of person 1 (grid[r1][c1]).<\/li>\n\n\n\n<li>If person 1 and person 2 are not in the same position (r1 != r2), consider the cherry at the current position of person 2.<\/li>\n\n\n\n<li>They can move in four possible movements (right, right), (right, down), (down, right), and (down, down).<\/li>\n<\/ol>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"410\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7-1024x410.png\" alt=\" four possible movements\" class=\"wp-image-1151\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7-1024x410.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7-300x120.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7-768x308.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7-750x300.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7-1140x457.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/Untitled-design-7.png 1276w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>We will Calculate the maximum number of cherries collected at each step by considering all four possibilities.<\/li>\n<\/ul>\n\n\n\n<p>Some of the edge cases of this problem are:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Either person goes out of bounds or encounters obstacles (-1) in the grid. In such cases, return INT_MIN as it signifies that the path is not possible<\/li>\n\n\n\n<li>If person 1 reaches the destination (n-1, n-1), return the value of the grid at that position.<\/li>\n\n\n\n<li>If both persons reach the destination simultaneously (r1 + c1 = r2 + c2), return the sum of the grid values at that position.<\/li>\n\n\n\n<li>We will use a 3D dynamic programming matrix to store intermediate results, avoiding redundant calculations.<\/li>\n\n\n\n<li>The three dimensions of the matrix represent the positions of the two persons and their distances from the origin.<\/li>\n\n\n\n<li>We will Check if the current state (positions of the two persons) already exists in the 3D dynamic programming matrix. If it does we will return the stored result to optimize computation.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program to solve the cherry pickup problem using dynamic programming:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint cherryPickupUtil(const vector&lt;vector&lt;int&gt;&gt;&amp; grid, vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;&amp; dp, int r1, int c1, int r2) {\n    int n = grid.size();\n    int c2 = r1 + c1 - r2;\n\n    \/\/ Check if out of bounds or encountering obstacles\n    if (r1 &gt;= n || c1 &gt;= n || r2 &gt;= n || c2 &gt;= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {\n        return INT_MIN;\n    }\n\n    \/\/ Check if already computed\n    if (dp[r1][c1][r2] != -1) {\n        return dp[r1][c1][r2];\n    }\n\n    \/\/ Base case: reached bottom-right corner\n    if (r1 == n - 1 &amp;&amp; c1 == n - 1) {\n        return grid[r1][c1];\n    }\n\n    \/\/ Calculate cherries collected at the current positions\n    int cherries = grid[r1][c1];\n    if (r1 != r2) {\n        cherries += grid[r2][c2];\n    }\n\n    \/\/ Calculate the maximum cherries for the two persons' movements\n    int maxCherries = cherries + max({\n        cherryPickupUtil(grid, dp, r1 + 1, c1, r2 + 1),\n        cherryPickupUtil(grid, dp, r1 + 1, c1, r2),\n        cherryPickupUtil(grid, dp, r1, c1 + 1, r2 + 1),\n        cherryPickupUtil(grid, dp, r1, c1 + 1, r2)\n    });\n\n    \/\/ Save the result in the memoization table\n    dp[r1][c1][r2] = maxCherries;\n\n    return maxCherries;\n}\n\nint main() {\n    vector&lt;vector&lt;int&gt;&gt; grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};\n    int n = grid.size();\n\n    \/\/ Memoization using a 3D vector\n    vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt; dp(n, vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(n, -1)));\n\n    \/\/ Start the recursion from the top-left corner\n    int result = max(0, cherryPickupUtil(grid, dp, 0, 0, 0));\n\n    cout &lt;&lt; &quot;Maximum cherries collected: &quot; &lt;&lt; result &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Here is the Java program to solve the cherry pickup problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class CherryPickup {\n\n    public static int cherryPickupUtil(int[][] grid, int[][][] dp, int r1, int c1, int r2) {\n        int n = grid.length;\n        int c2 = r1 + c1 - r2;\n\n        \/\/ Check if out of bounds or encountering obstacles\n        if (r1 &gt;= n || c1 &gt;= n || r2 &gt;= n || c2 &gt;= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {\n            return Integer.MIN_VALUE;\n        }\n\n        \/\/ Check if already computed\n        if (dp[r1][c1][r2] != -1) {\n            return dp[r1][c1][r2];\n        }\n\n        \/\/ Base case: reached bottom-right corner\n        if (r1 == n - 1 &amp;&amp; c1 == n - 1) {\n            return grid[r1][c1];\n        }\n\n        \/\/ Calculate cherries collected at the current positions\n        int cherries = grid[r1][c1];\n        if (r1 != r2) {\n            cherries += grid[r2][c2];\n        }\n\n        \/\/ Calculate the maximum cherries for the two persons' movements\n        int maxCherries = cherries + Math.max(\n                Math.max(cherryPickupUtil(grid, dp, r1 + 1, c1, r2 + 1),\n                        cherryPickupUtil(grid, dp, r1 + 1, c1, r2)),\n                Math.max(cherryPickupUtil(grid, dp, r1, c1 + 1, r2 + 1),\n                        cherryPickupUtil(grid, dp, r1, c1 + 1, r2)));\n\n        \/\/ Save the result in the memoization table\n        dp[r1][c1][r2] = maxCherries;\n\n        return maxCherries;\n    }\n\n    public static void main(String[] args) {\n        int[][] grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};\n        int n = grid.length;\n\n        \/\/ Memoization using a 3D array\n        int[][][] dp = new int[n][n][n];\n        for (int[][] layer : dp) {\n            for (int[] row : layer) {\n                Arrays.fill(row, -1);\n            }\n        }\n\n        \/\/ Start the recursion from the top-left corner\n        int result = Math.max(0, cherryPickupUtil(grid, dp, 0, 0, 0));\n\n        System.out.println(&quot;Maximum cherries collected: &quot; + result);\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>You can implement it in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def cherry_pickup_util(grid, dp, r1, c1, r2):\n    n = len(grid)\n    c2 = r1 + c1 - r2\n\n    # Check if out of bounds or encountering obstacles\n    if r1 &gt;= n or c1 &gt;= n or r2 &gt;= n or c2 &gt;= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:\n        return float('-inf')\n\n    # Check if already computed\n    if dp[r1][c1][r2] != -1:\n        return dp[r1][c1][r2]\n\n    # Base case: reached bottom-right corner\n    if r1 == n - 1 and c1 == n - 1:\n        return grid[r1][c1]\n\n    # Calculate cherries collected at the current positions\n    cherries = grid[r1][c1]\n    if r1 != r2:\n        cherries += grid[r2][c2]\n\n    # Calculate the maximum cherries for the two persons' movements\n    max_cherries = cherries + max(\n        cherry_pickup_util(grid, dp, r1 + 1, c1, r2 + 1),\n        cherry_pickup_util(grid, dp, r1 + 1, c1, r2),\n        cherry_pickup_util(grid, dp, r1, c1 + 1, r2 + 1),\n        cherry_pickup_util(grid, dp, r1, c1 + 1, r2)\n    )\n\n    # Save the result in the memoization table\n    dp[r1][c1][r2] = max_cherries\n\n    return max_cherries\n\n\ndef main():\n    grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]\n    n = len(grid)\n\n    # Memoization using a 3D list\n    dp = [[[-1] * n for _ in range(n)] for _ in range(n)]\n\n    # Start the recursion from the top-left corner\n    result = max(0, cherry_pickup_util(grid, dp, 0, 0, 0))\n\n    print(&quot;Maximum cherries collected:&quot;, result)\n\n\nif __name__ == &quot;__main__&quot;:\n    main()<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>Maximum cherries collected: 5<\/code><\/pre>\n\n\n\n<p><strong>The time complexity for the dynamic programming approach to solve the cherry pickup problem is O(N<sup>3<\/sup>) because it is determined by the number of unique states that the recursive function explores.<\/strong> In this case, the number of unique states is determined by the positions of the two persons and their distances from the origin.<\/p>\n\n\n\n<p>The space complexity for this approach is&nbsp; O(N<sup>3<\/sup>) because the 3D array is used for storing the results of subproblems to avoid redundant calculations.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, we have used a dynamic programming approach, and the concept of two persons traversing the grid simultaneously, an efficient solution to maximize cherry collection. This strategy ensures that the combined efforts of the two persons result in the optimal collection of cherries.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand the Cherry Pickup problem from leetcode and how to solve it using dynamic programming approach.<\/p>\n","protected":false},"author":12,"featured_media":1148,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1146","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1146"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1146\/revisions"}],"predecessor-version":[{"id":1188,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1146\/revisions\/1188"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1148"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}