<p>You are given an <code>n x n</code> <code>grid</code> representing a field of cherries, each cell is one of three possible integers.</p>

<ul>
	<li><code>0</code> means the cell is empty, so you can pass through,</li>
	<li><code>1</code> means the cell contains a cherry that you can pick up and pass through, or</li>
	<li><code>-1</code> means the cell contains a thorn that blocks your way.</li>
</ul>

<p>Return <em>the maximum number of cherries you can collect by following the rules below</em>:</p>

<ul>
	<li>Starting at the position <code>(0, 0)</code> and reaching <code>(n - 1, n - 1)</code> by moving right or down through valid path cells (cells with value <code>0</code> or <code>1</code>).</li>
	<li>After reaching <code>(n - 1, n - 1)</code>, returning to <code>(0, 0)</code> by moving left or up through valid path cells.</li>
	<li>When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell <code>0</code>.</li>
	<li>If there is no valid path between <code>(0, 0)</code> and <code>(n - 1, n - 1)</code>, then no cherries can be collected.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/14/grid.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,-1],[1,0,-1],[1,1,1]]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
<strong>Output:</strong> 0
</pre>

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

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>grid[i][j]</code> is <code>-1</code>, <code>0</code>, or <code>1</code>.</li>
	<li><code>grid[0][0] != -1</code></li>
	<li><code>grid[n - 1][n - 1] != -1</code></li>
</ul>

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:

        # Some approaches:
        # (1) can do DFS + backtracking for both paths. Too many paths though. Could reduce with some followup DP, but the
        #     paths "interact" so you have to be careful
        # (2) can try dynamic programming where you build the first half of the down path, then have some optimal subproblem
        #     solution for the rest of down plus up. Not clear how you'd do that though
        # (3) down and then up can be thought of as having two different down paths. can probably write it as C[r][c1][c2] where c1 <= c2
        #      because we can go down and right, and once you go right you can't go back. so one path will be to the right of the other, and stay there
        #     will paths ever cross? unlikely. maybe not really relevant. we'll see below

        # so we can have the best solution where the paths go from (0, 0) to (r,c1) and (r,c2)
        # from (r, c1) and (r,c2), each path can move R steps to the right, then down

        # maybe better to think about the case in reverse: to get to (r,c1) and (r, c2)
        #   path 1 had to come from (r,c1-1) or (r-1,c1)
        #   path 2 had to come from (r,c2-1) or (r-1,c2)
        #
        # Let B[r][c1][c2] be the best solution for two paths from (0,0) to (r,c1) and (r,c2)
        # Then the four alternatives (2 per path) work out to
        #   B[r][c1][c2] = -1 if (r,c1) or (r,c2) are impassable terrain
        #                = max(B[r][c1-1][c2-1], ???) # uh-oh... what about when r for left != r for right??

        # probably need a fourth variable: the paths are at r1,c1 and r2,c2 after n moves.
        # they move in lockstep though so I don't think there are actually four variables
        # but let's for ahead with four vars and see if we can reduce to 3 later

        # for four variables we have B[r1][c1][r2][c2]
        #   at each step r1,c1 and r2,c2 we had to move down or left for both
        #   so
        #       -1       if either cell is -1 (thorn)
        #       best of  B[r1-1][c1][r2-1][c2]     # so r1+c1 == k == r2+c2, so c1=k-r1 and c2=k-r2. So same info is in some B[k][r1][r2]
        #                B[r1][c1-1][r2-1][c2]
        #                B[r1-1][c1][r2][c2-1]
        #                B[r1][c1-1][r2][c2-2]
        #                   PLUS grid[r1][c1] + grid[r2][c2] if they're different cells
        #                   PLUS grid[r1][c1] if they're the same cell
        #    B[k][..] depends only on B[k-1][..] so we now have an O(N^2) space and O(N^3) time solution!

        # are there more considerations, e.g. do we need to worry about retracing paths for the +1/+2?
        #   e.g. is it possible for r1,c1 that the other path travsed it in a previous step k' < k?
        #        for r1,c1, k = r1+c1. for path 2 to have already been there, it would have happened at k'=r1+c2 = k.
        #        So no, it's not possible.

        # I hypothesize further that wlog we'll never trace paths where path 1 is right of path 2 for a given row..
        # but this condition seems hard to enforce because we use a k,r1,r2-centric solution.

        # N = len(grid)
        # prev = [[0]*N for _ in range(N)]
        # curr = [[0]*N for _ in range(N)]
        # prev[0][0] = grid[0][0]

        # for k in range(1,2*N+1):
        #     #
        #     for r1 in range(max(k-N+1, 0), min(k+1,N)): # c1 >= 0 and c1 < N ====> k-r1 >= 0 and k-r1 < N ===> r1 <= k and r1 > k-N
        #         c1 = k-r1
        #         for r2 in range(max(k-N+1, 0), min(k+1,N)):
        #             c2 = k-r2

        #             # TODO: reorder checks for speed
        #             if grid[r1][c1] < 0 or grid[r2][c2] < 0:
        #                 curr[r1][r2] = -1 # illegal state
        #             else:
        #                 b = -1
        #                 # up to four source cells: UU, UL, LU, LL
        #                 if r1 > 0 and r2 > 0: # UU
        #                     b = prev[r1-1][r2-1]
        #                 if r1 > 0 and c2 > 0: # UL
        #                     b = max(b, prev[r1-1][r2])
        #                 if c1 > 0 and r2 > 0: # LU
        #                     b = max(b, prev[r1][r2-1])
        #                 if c1 > 0 and c2 > 0: # LL
        #                     b = max(b, prev[r1][r2])
                        
        #                 if b == -1:
        #                     curr[r1][r2] = -1
        #                 else:
        #                     if r1 == r2:
        #                         curr[r1][r2] = b + grid[r1][c1]
        #                     else:
        #                         curr[r1][r2] = b + grid[r1][c1] + grid[r2][c2]

        #     prev, curr = curr, prev

        # return max(prev[-1][-1], 0) # both paths at -1,-1. max with zero converts -1 to 0

        # FT about 40%
        # Fastest solutions use DFS + caching!!
        #    In retrospect, there are some signs that this would be the case:
        #       only part of the dp grid is filled out at a time
        #       we fill out DP grid for all cells, even those where there is no path to the solution
        # So we could find all such cells not reachable from (-1,-1) and ignore them in the DP array
        # Or we can organically avoid them by the nature of DFS

        # brute force DP: be at r1,c1,r2,c2 and take best of four earlier solutions
        # some improvements: at each step we back up by 1 step, both paths have taken the same number of steps
        # so reformulate as k,r1,r2
        # Furthermore, wlog we can say one path is at least as low as the other
        bad = float('-inf')

        @functools.cache
        def dfs(k: int, r1: int, r2: int):
            # print(r1, k-r1, r2, k-r2)

            if r1 < 0 or r2 < 0 or r1 > r2:
                return bad

            c1 = k-r1
            c2 = k-r2

            if c1 < 0 or c2 < 0:
                return bad

            if k == 0:
                return grid[0][0] # first step, r1 == .. == c2 == 0

            if grid[r1][c1] < 0 or grid[r2][c2] < 0:
                return bad

            prev = max(
                dfs(k-1, r1, r2),
                dfs(k-1, r1-1, r2),
                dfs(k-1, r1, r2-1),
                dfs(k-1, r1-1, r2-1)
            )

            if r1 == r2:
                return prev + grid[r1][c1]
            else:
                return prev + grid[r1][c1] + grid[r2][c2]

        N = len(grid)
        return max(dfs(2*N-2, N-1, N-1), 0)
37666