<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:
    # https://leetcode.com/problems/cherry-pickup/solutions/3811789/dp-and-dfs-solutions-with-a-different-and-hopefully-simpler-explanations-ft-100/
    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):
            # 这道题的关键是：
            # * 想到2条路同时dfs这种方案（需要四种回溯）
            # * 而且要能想到两条路同时从上往下和一次向下一次向上都是一样的结果（因为是同一个path）
            # * 而且两次简单的DP不能解决问题（他并没有解释只是说两次greedy不见得是答案）
            # print(r1, k-r1, r2, k-r2)
            # 为什么r1 > r2是非法？答案是没有必要检查 r1 > r2
            if r1 < 0 or r2 < 0:
                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)
            )

            # 之所以上面返回float('-inf')是为了方便这里
            # 如果四条路都返回-inf，那么无论当前怎么样最终还是-inf
            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)
60626