<p>You are given a <code>rows x cols</code> matrix <code>grid</code> representing a field of cherries where <code>grid[i][j]</code> represents the number of cherries that you can collect from the <code>(i, j)</code> cell.</p>

<p>You have two robots that can collect cherries for you:</p>

<ul>
	<li><strong>Robot #1</strong> is located at the <strong>top-left corner</strong> <code>(0, 0)</code>, and</li>
	<li><strong>Robot #2</strong> is located at the <strong>top-right corner</strong> <code>(0, cols - 1)</code>.</li>
</ul>

<p>Return <em>the maximum number of cherries collection using both robots by following the rules below</em>:</p>

<ul>
	<li>From a cell <code>(i, j)</code>, robots can move to cell <code>(i + 1, j - 1)</code>, <code>(i + 1, j)</code>, or <code>(i + 1, j + 1)</code>.</li>
	<li>When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.</li>
	<li>When both robots stay in the same cell, only one takes the cherries.</li>
	<li>Both robots cannot move outside of the grid at any moment.</li>
	<li>Both robots should reach the bottom row in <code>grid</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_1_1802.png" style="width: 374px; height: 501px;" />
<pre>
<strong>Input:</strong> grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/sample_2_1802.png" style="width: 500px; height: 452px;" />
<pre>
<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]]
<strong>Output:</strong> 28
<strong>Explanation:</strong> Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>rows == grid.length</code></li>
	<li><code>cols == grid[i].length</code></li>
	<li><code>2 &lt;= rows, cols &lt;= 70</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>
</ul>

import itertools

class State:
    col1 = 0
    col2 = 0
    row = 0

    def __init__(self, col1, col2, row):
        self.col1 = col1
        self.col2 = col2
        self.row = row

    def __hash__(self):
        return hash("{}_{}_{}".format(self.col1, self.col2, self.row))

    def __eq__(self, other):
        return self.col1 == other.col1 and self.col2 == other.col2 and self.row == other.row
    
    def __str__(self):
        return "{}_{}_{}".format(self.col1, self.col2, self.row)

class Solution:
    # State space gride mapping from [col1, col2, row] to max total_cherries achievable starting from there
    state_max_map = dict()

    # Iterate down with DP
    def calculate_max(self, state, grid) -> int:
        print(state)

        num_rows = len(grid)
        num_cols = 0 if num_rows == 0 else len(grid[0])
        
        row_cherries = grid[state.row][state.col1] + (grid[state.row][state.col2] if (state.col1 != state.col2) else 0)

        if state.row == num_rows - 1:
            return row_cherries
    
        next_states = []
        
        for i, j in itertools.product(range(-1, 2), range(-1, 2)):
            next_col1 = max(0, min(num_cols - 1, state.col1 + i))
            next_col2 = max(0, min(num_cols - 1, state.col2 + j))
            next_states.append(State(next_col1, next_col2, state.row + 1))

        next_cherries = []

        for s in next_states:
            if not s in self.state_max_map.keys():
                max_cherries = self.calculate_max(s, grid)
                self.state_max_map[s] = max_cherries
                print(s, max_cherries)

            next_cherries.append(self.state_max_map[s])

        return max(next_cherries) + row_cherries

    def cherryPickup(self, grid) -> int:
        self.state_max_map = dict()

        num_rows = len(grid)
        num_cols = 0 if num_rows == 0 else len(grid[0])

        if num_rows == 0:
            return 0
        elif num_rows == 1:
            return grid[0][0] + grid[0][len(grid[0]) - 1]

        return self.calculate_max(State(0, num_cols -1, 0), grid)
39628