<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>

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        # robots can only move down to three cells
        # 想过用记忆化搜索，但我的想法是分两次，但是分两次了就不可以同时两个bot往下了，算法是错的

        m = len(grid)
        n = len(grid[0])

        dp = [[[0] * (n+2) for _ in range(n+2)] for _ in range(m+1)]
        # 1：1翻译成递推
        # 缩小j和k的范围，就算一直往右下走，j最大也就是i。k同理，但是j和k相等没有意义，两个机器人没必要到同一个格子
        # 一般来说是n+1，m+1，因为现在要考虑两边的越界情况，所以加2了
        for i in range(m-1, -1, -1):
            for j in range(min(n, i+1)):
                for k in range(max(j+1, n-i-1), n):
                    dp[i][j+1][k+1] = max(dp[i+1][j][k], dp[i+1][j][k+1], dp[i+1][j][k+2], dp[i+1][j+1][k], 
                    dp[i+1][j+1][k+1], dp[i+1][j+1][k+2], dp[i+1][j+2][k], dp[i+1][j+2][k+1], dp[i+1][j+2][k+2]) + \
                    grid[i][j] + grid[i][k]
    
        return dp[0][1][n]



        @cache
        def dfs(i, j, k):
            if i == m or j < 0 or j >= n or k < 0 or k >= n:
                return 0
            return max(dfs(i + 1, j2, k2) for j2 in (j - 1, j, j + 1) for k2 in (k - 1, k, k + 1)) + \
                   grid[i][j] + (grid[i][k] if k != j else 0)

            # if j == k:
            #     val = grid[i][j]
            # else:
            #     val = grid[i][j] + grid[i][k]
            
            # return val + max(dfs(i+1, j-1, k), dfs(i+1, j, k), dfs(i+1, j+1, k), dfs(i+1, j-1, k-1),
            # dfs(i+1, j-1, k+1), dfs(i+1, j, k-1), dfs(i+1, j, k+1), dfs(i+1, j+1, k-1), dfs(i+1, j+1, k+1))
        return dfs(0, 0, n-1)

            

            

22501