{"id":873,"date":"2025-08-11T16:50:20","date_gmt":"2025-08-11T11:20:20","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=873"},"modified":"2025-08-11T16:50:24","modified_gmt":"2025-08-11T11:20:24","slug":"cherry-pickup-ii","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/","title":{"rendered":"Cherry Pickup II | Leetcode 1463 | Solved using Dynamic Programming"},"content":{"rendered":"\n<p>You are given a&nbsp;<code>rows x cols<\/code>&nbsp;matrix&nbsp;<code>grid<\/code>&nbsp;representing a field of cherries where&nbsp;<code>grid[i][j]<\/code>&nbsp;represents the number of cherries that you can collect from the&nbsp;<code>(i, j)<\/code>&nbsp;cell.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/cherry-pickup-ii\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p>You have two robots that can collect cherries for you:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Robot #1<\/strong>\u00a0is located at the\u00a0<strong>top-left corner<\/strong>\u00a0<code>(0, 0)<\/code>, and<\/li>\n\n\n\n<li><strong>Robot #2<\/strong>\u00a0is located at the\u00a0<strong>top-right corner<\/strong>\u00a0<code>(0, cols - 1)<\/code>.<\/li>\n<\/ul>\n\n\n\n<p>Return&nbsp;<em>the maximum number of cherries collection using both robots by following the rules below<\/em>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>From a cell\u00a0<code>(i, j)<\/code>, robots can move to cell\u00a0<code>(i + 1, j - 1)<\/code>,\u00a0<code>(i + 1, j)<\/code>, or\u00a0<code>(i + 1, j + 1)<\/code>.<\/li>\n\n\n\n<li>When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.<\/li>\n\n\n\n<li>When both robots stay in the same cell, only one takes the cherries.<\/li>\n\n\n\n<li>Both robots cannot move outside of the grid at any moment.<\/li>\n\n\n\n<li>Both robots should reach the bottom row in\u00a0<code>grid<\/code>.<\/li>\n<\/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\"><strong>Input:<\/strong> grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]<br><strong>Output:<\/strong> 24<br><strong>Explanation:<\/strong> Path of robot #1 and #2 are described in color green and blue respectively.<br>Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.<br>Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.<br>Total of cherries: 12 + 12 = 24.<\/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\"><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]]<br><strong>Output:<\/strong> 28<br><strong>Explanation:<\/strong> Path of robot #1 and #2 are described in color green and blue respectively.<br>Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.<br>Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.<br>Total of cherries: 17 + 11 = 28.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>rows == grid.length<\/code><\/li>\n\n\n\n<li><code>cols == grid[i].length<\/code><\/li>\n\n\n\n<li><code>2 &lt;= rows, cols &lt;= 70<\/code><\/li>\n\n\n\n<li><code>0 &lt;= grid[i][j] &lt;= 100<\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-09af9235-f5db-4b52-ac8f-84103e8f2fe2\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#0-solution-1-recursion-brute-force\" style=\"\">Solution 1: Recursion (Brute Force)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#5-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#6-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#7-solution-2-memoization-top-down-dp\" style=\"\">Solution 2: Memoization (Top-Down DP)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#8-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#9-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#10-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#11-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#12-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#13-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#14-solution-3-tabulation-bottom-up-dp\" style=\"\">Solution 3: Tabulation (Bottom-Up DP)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#15-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#16-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#17-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#18-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#19-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#20-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#21-solution-4-tabulation-space-optimization\" style=\"\">Solution 4: Tabulation (Space Optimization)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#22-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#23-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#24-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#25-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#26-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#27-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/cherry-pickup-ii\/#28-final-notes-and-tips\" style=\"\">Final Notes and Tips<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-recursion-brute-force\">Solution 1: Recursion (Brute Force)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Model the process as both robots moving row by row. At each row i, robot 1 can move to j1 + {-1, 0, +1}, and robot 2 to j2 + {-1, 0, +1}. For each pair of moves (3 x 3 = 9 combinations), compute cherries collected on current row and add the maximum of the recursive results for the next row. If both robots are on the same cell, count grid[i][j1] once; otherwise, sum grid[i][j1] + grid[i][j2]. Out-of-bound moves yield negative infinity to invalidate those paths.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Base conditions:\n<ul class=\"wp-block-list\">\n<li>If any column is out of bounds, return -inf to invalidate.<\/li>\n\n\n\n<li>If at the last row, return grid[i][j1] if j1 == j2 else grid[i][j1] + grid[i][j2].<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Transition:\n<ul class=\"wp-block-list\">\n<li>Try all 9 moves for (new_j1, new_j2) in {-1, 0, +1} x {-1, 0, +1}, accumulate current cherries, and take the maximum.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, i, j1, j2, grid):\n        # If any robot goes out of bounds, path is invalid\n        if j1 &lt; 0 or j1 &gt;= len(grid[0]) or j2 &lt; 0 or j2 &gt;= len(grid):\n            return float(&quot;-inf&quot;)\n        # If last row: collect once if same cell else sum both\n        if i == len(grid) - 1:\n            if j1 == j2:\n                return grid[i][j1]\n            return grid[i][j1] + grid[i][j2]\n        maxi = 0\n        # Explore all 9 move combinations for both robots\n        for new_j1 in range(-1, 2):\n            for new_j2 in range(-1, 2):\n                if j1 == j2:\n                    ans = grid[i][j1] + self.solve(\n                        i + 1, j1 + new_j1, j2 + new_j2, grid\n                    )\n                else:\n                    ans = (\n                        grid[i][j1]\n                        + grid[i][j2]\n                        + self.solve(i + 1, j1 + new_j1, j2 + new_j2, grid)\n                    )\n                maxi = max(maxi, ans)\n        return maxi\n\n    def cherryPickup(self, grid: List[List[int]]) -&gt; int:\n        # Start with robot1 at col 0 and robot2 at col m-1\n        return self.solve(0, 0, len(grid) - 1, grid)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j2<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># If any robot goes out of bounds, path is invalid<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j1 &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]) <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;-inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># If last row: collect once if same cell else sum both<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid) - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[i][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[i][j1] + grid[i][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Explore all 9 move combinations for both robots<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans = grid[i][j1] + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j1 + new_j1, j2 + new_j2, grid<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans = (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        grid[i][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        + grid[i][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j1 + new_j1, j2 + new_j2, grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> maxi<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">cherryPickup<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Start with robot1 at col 0 and robot2 at col m-1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid) - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, grid)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The recursive function explores all combinations of moves for both robots.<\/li>\n\n\n\n<li>It ensures invalid moves are discarded and correctly handles the \u201csame cell\u201d case.<\/li>\n\n\n\n<li>The main function starts from the top row with robots at columns 0 and m-1.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise<\/strong>: Time O(9^(n)) in worst case due to branching over 9 moves per row; Space O(n) for recursion depth.<\/li>\n\n\n\n<li><strong>Simplified<\/strong>: Exponential time; linear recursion space.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-conclusion\">Conclusion<\/h3>\n\n\n\n<p>This gives the right answer but is impractical for larger <strong>n <\/strong>and <strong>m <\/strong>due to heavy recomputation.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-solution-2-memoization-top-down-dp\">Solution 2: Memoization (Top-Down DP)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-intuition\">Intuition<\/h3>\n\n\n\n<p>The recursive state repeats for the same <strong>(i, j1, j2)<\/strong>. Cache the maximum cherries for each state in a <strong>3D DP<\/strong> table <strong>dp[i][j1][j2]<\/strong>. This reduces the complexity dramatically since each state is computed once.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use dp with dimensions <strong>n x m x m<\/strong> initialized to <strong>-1.<\/strong><\/li>\n\n\n\n<li>Before computing a state, return <strong>dp[i][j1][j2]<\/strong> if it\u2019s already known.<\/li>\n\n\n\n<li>Otherwise, compute as in recursion, store the best in <strong>dp[i][j1][j2]<\/strong>, and return it.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, i, j1, j2, grid, dp):\n        # Boundary checks\n        if j1 &lt; 0 or j1 &gt;= len(grid) or j2 &lt; 0 or j2 &gt;= len(grid):\n            return float(&quot;-inf&quot;)\n        # Base case at last row\n        if i == len(grid) - 1:\n            if j1 == j2:\n                return grid[i][j1]\n            return grid[i][j1] + grid[i][j2]\n        # Return cached result if computed\n        if dp[i][j1][j2] != -1:\n            return dp[i][j1][j2]\n        maxi = 0\n        # Try all move pairs\n        for new_j1 in range(-1, 2):\n            for new_j2 in range(-1, 2):\n                if j1 == j2:\n                    ans = grid[i][j1] + self.solve(\n                        i + 1, j1 + new_j1, j2 + new_j2, grid, dp\n                    )\n                else:\n                    ans = (\n                        grid[i][j1]\n                        + grid[i][j2]\n                        + self.solve(i + 1, j1 + new_j1, j2 + new_j2, grid, dp)\n                    )\n                maxi = max(maxi, ans)\n        dp[i][j1][j2] = maxi\n        return dp[i][j1][j2]\n\n    def cherryPickup(self, grid: List[List[int]]) -&gt; int:\n        n = len(grid)\n        m = len(grid)\n        # DP dimensions: N x M x M\n        dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]\n        return self.solve(0, 0, len(grid) - 1, grid, dp)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j2<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">dp<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Boundary checks<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j1 &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid) <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;-inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case at last row<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid) - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[i][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[i][j1] + grid[i][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Return cached result if computed<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dp[i][j1][j2] != -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[i][j1][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try all move pairs<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans = grid[i][j1] + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j1 + new_j1, j2 + new_j2, grid, dp<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans = (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        grid[i][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        + grid[i][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j1 + new_j1, j2 + new_j2, grid, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[i][j1][j2] = maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[i][j1][j2]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">cherryPickup<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># DP dimensions: N x M x M<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid) - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, grid, dp)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The memo table stores the best result for every (row, col1, col2).<\/li>\n\n\n\n<li>This eliminates overlapping subproblems and makes the solution efficient.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise<\/strong>: Time O(n \u00d7 m \u00d7 m \u00d7 9) \u2248 O(n \u00d7 m\u00b2); Space O(n \u00d7 m\u00b2) for dp plus O(n) recursion stack.<\/li>\n\n\n\n<li><strong>Simplified<\/strong>: Time O(n m\u00b2), Space O(n m\u00b2).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Memoization turns the exponential recursion into a polynomial-time solution suitable for constraints up to 70.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"14-solution-3-tabulation-bottom-up-dp\">Solution 3: Tabulation (Bottom-Up DP)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-intuition\">Intuition<\/h3>\n\n\n\n<p>Build dp from the last row upward. For each row i and column pair (j1, j2), compute the best by considering all next moves (9 options) using the values from row i+1. Initialize the base row directly from the grid.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Define dp[i][j1][j2]<\/strong> = maximum cherries from row i when robots are at (j1, j2).<\/li>\n\n\n\n<li><strong>Base<\/strong>: For i = n-1, dp[n-1][j1][j2] = grid[n-1][j1] if j1 == j2 else grid[n-1][j1] + grid[n-1][j2].<\/li>\n\n\n\n<li><strong>Transition<\/strong>: For each i from n-2 down to 0, and each j1, j2, compute max over valid next positions using dp[i+1][\u2026].<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def cherryPickup(self, grid: List[List[int]]) -&gt; int:\n        n = len(grid)\n        m = len(grid)\n        dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]\n        # Base cases for last row\n        for j1 in range(m):\n            for j2 in range(m):\n                if j1 == j2:\n                    dp[n - 1][j1][j2] = grid[n - 1][j1]\n                else:\n                    dp[n - 1][j1][j2] = grid[n - 1][j1] + grid[n - 1][j2]\n        # Fill from bottom to top\n        for i in range(n - 2, -1, -1):\n            for j1 in range(m):\n                for j2 in range(m):\n                    maxi = 0\n                    for new_j1 in range(-1, 2):\n                        for new_j2 in range(-1, 2):\n                            if (\n                                j1 + new_j1 &lt; 0\n                                or j2 + new_j2 &lt; 0\n                                or j1 + new_j1 &gt;= m\n                                or j2 + new_j2 &gt;= m\n                            ):\n                                ans = float(&quot;-inf&quot;)\n                            elif j1 == j2:\n                                ans = grid[i][j1] + dp[i + 1][j1 + new_j1][j2 + new_j2]\n                            else:\n                                ans = (\n                                    grid[i][j1]\n                                    + grid[i][j2]\n                                    + dp[i + 1][j1 + new_j1][j2 + new_j2]\n                                )\n                            maxi = max(maxi, ans)\n                    dp[i][j1][j2] = maxi\n        return dp[0][0][m - 1]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">cherryPickup<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base cases for last row<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    dp[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1][j2] = grid[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    dp[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1][j2] = grid[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1] + grid[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Fill from bottom to top<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                j1 + new_j1 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 + new_j2 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j1 + new_j1 &gt;= m<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 + new_j2 &gt;= m<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            ):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                ans = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;-inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                ans = grid[i][j1] + dp[i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1 + new_j1][j2 + new_j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                ans = (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                    grid[i][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                    + grid[i][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                    + dp[i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1 + new_j1][j2 + new_j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    dp[i][j1][j2] = maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][m - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"18-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initializes the last row where only immediate cherries matter.<\/li>\n\n\n\n<li>For each upper row, aggregates the best future gains from the next row by exploring 9 possibilities.<\/li>\n\n\n\n<li>The final answer is dp[m-1], matching the start positions.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise<\/strong>: Time O(n \u00d7 m \u00d7 m \u00d7 9) \u2248 O(n \u00d7 m\u00b2); Space O(n \u00d7 m\u00b2).<\/li>\n\n\n\n<li><strong>Simplified<\/strong>: Time O(n m\u00b2), Space O(n m\u00b2).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-conclusion\">Conclusion<\/h3>\n\n\n\n<p>This bottom-up approach avoids recursion and is easy to iterate and debug.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"21-solution-4-tabulation-space-optimization\">Solution 4: Tabulation (Space Optimization)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"22-intuition\">Intuition<\/h3>\n\n\n\n<p>At row i, you only need results from row i+1. Replace the 3D dp with two 2D layers: prev for row i+1 and curr for row i. Roll these layers as you move up to save memory from O(n m\u00b2) to O(m\u00b2).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"23-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initialize prev as the base row (n-1).<\/li>\n\n\n\n<li>For each upper row, compute curr[j1][j2] using prev for next positions.<\/li>\n\n\n\n<li>After finishing a row, set prev = curr and continue upward.<\/li>\n\n\n\n<li>Final answer is in prev[m-1] after processing row 0.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"24-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def cherryPickup(self, grid: List[List[int]]) -&gt; int:\n        n = len(grid)\n        m = len(grid)\n        # Base: last row layer\n        prev = [[-1 for _ in range(m)] for _ in range(m)]\n        for j1 in range(m):\n            for j2 in range(m):\n                if j1 == j2:\n                    prev[j1][j2] = grid[n - 1][j1]\n                else:\n                    prev[j1][j2] = grid[n - 1][j1] + grid[n - 1][j2]\n        # Build upwards using rolling 2D arrays\n        for i in range(n - 2, -1, -1):\n            curr = [[-1 for _ in range(m)] for _ in range(m)]\n            for j1 in range(m):\n                for j2 in range(m):\n                    maxi = 0\n                    for new_j1 in range(-1, 2):\n                        for new_j2 in range(-1, 2):\n                            if (\n                                j1 + new_j1 &lt; 0\n                                or j2 + new_j2 &lt; 0\n                                or j1 + new_j1 &gt;= m\n                                or j2 + new_j2 &gt;= m\n                            ):\n                                ans = float(&quot;-inf&quot;)\n                            elif j1 == j2:\n                                ans = grid[i][j1] + prev[j1 + new_j1][j2 + new_j2]\n                            else:\n                                ans = (\n                                    grid[i][j1]\n                                    + grid[i][j2]\n                                    + prev[j1 + new_j1][j2 + new_j2]\n                                )\n                            maxi = max(maxi, ans)\n                    curr[j1][j2] = maxi\n            prev = curr\n        return prev[m - 1]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">cherryPickup<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base: last row layer<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    prev[j1][j2] = grid[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    prev[j1][j2] = grid[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j1] + grid[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Build upwards using rolling 2D arrays<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            curr = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> new_j2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                j1 + new_j1 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 + new_j2 &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j1 + new_j1 &gt;= m<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j2 + new_j2 &gt;= m<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            ):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                ans = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;-inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> j1 == j2:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                ans = grid[i][j1] + prev[j1 + new_j1][j2 + new_j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                ans = (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                    grid[i][j1]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                    + grid[i][j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                    + prev[j1 + new_j1][j2 + new_j2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                                )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                            maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    curr[j1][j2] = maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = curr<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> prev[m - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"25-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Stores only two layers at any time: the current row\u2019s DP and the next row\u2019s DP.<\/li>\n\n\n\n<li>Uses the same transition logic as tabulation but with reduced memory.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"26-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: Time O(n \u00d7 m \u00d7 m \u00d7 9) \u2248 O(n \u00d7 m\u00b2); Space O(m\u00b2) for two 2D layers.<\/li>\n\n\n\n<li>Simplified: Time O(n m\u00b2), Space O(m\u00b2).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"27-conclusion\">Conclusion<\/h3>\n\n\n\n<p>This is the interview-ready optimal DP: minimal space with the same time complexity and clean rolling-state logic.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"28-final-notes-and-tips\">Final Notes and Tips<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Always handle the \u201csame cell\u201d case by counting cherries once.<\/li>\n\n\n\n<li>Use -inf for invalid moves to naturally exclude them from max computations.<\/li>\n\n\n\n<li>The 3D state (i, j1, j2) encodes both robots\u2019 positions; transitions are the 9 combined moves per step.<\/li>\n\n\n\n<li>For constraints up to 70&#215;70, O(n m\u00b2) with memoization or tabulation runs comfortably.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;rows x cols&nbsp;matrix&nbsp;grid&nbsp;representing a field of cherries where&nbsp;grid[i][j]&nbsp;represents the number of cherries that you can collect from the&nbsp;(i, j)&nbsp;cell. Here&#8217;s the [Problem Link] to begin with. You have two robots that can collect cherries for you: Return&nbsp;the maximum number of cherries collection using both robots by following the rules below: Example 1:<\/p>\n","protected":false},"author":1,"featured_media":876,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,5],"tags":[38,18],"class_list":{"0":"post-873","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-dynamic-programming-on-2d-arrays","10":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/cherry-pickup-II-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/873","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=873"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/873\/revisions"}],"predecessor-version":[{"id":877,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/873\/revisions\/877"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/876"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}