First of all, greedy method does not work here. That is:

Maximizing the first one-way for cherries does NOT guarantee maximized cherries for round-trip.

The reason is that the problem allows only shortest path moving and greedy method does not do a good overall planning.

**Counter Example:**

`0`

1 -1

`1 1`

-1

1 `1 0`

If the first one-way goes along the red path for maximal 3 cherries, it splits the remaining 2 cherries into opposite sides of the diagonal which is impossible for round trip to pick up all cherries.

**Define DP variable**: so we have to plan the round trip altogether. Note that the path direction is irrelevant to the problem and we are forced to move only on shortest paths.

Define

`dp[i][j][L]`

= the max cherries picked up from`(0,0)`

along two shortest paths reaching`(i,L-i)`

and`(j,L-j)`

, respectively.

Note that each path length is exactly `L`

, so the answer is to compute `dp[n-1][n-1][2*(n-1)]`

.

To reach cells `(i,L-i)`

and `(j,L-j)`

, you have to reach their left or top cells with any combination, which leads to the DP equation:

```
dp[i][j][L] = max(dp[i-a][j-b][L-1] for a, b = 0 or 1) + grid[i][L-i] + grid[j][L-j]
```

To optimize time/space complexity, note that

`(i,j)`

is symmetric, so why not just compute for`i<=j`

.`(i,j,L)`

has constraint:`max(L-n+1,0) <= i <= j <= min(L,n-1)`

.`dp[][][L]`

depends on only`dp[][][L-1]`

, so no need to allocation`O(n)`

space in`L`

dimension.

```
int cherryPickup(vector<vector<int>>& grid)
{
int n = grid.size();
vector<vector<int>> cur(n, vector<int>(n,-1)), next = cur;
cur[0][0] = grid[0][0];
// cur[i][j] is set for i<=j
auto Cur = [&](int i, int j) { return 0<=min(i,j) && max(i,j)<n? cur[min(i,j)][max(i,j)] : -1; };
for (int L = 1; L <= 2*(n-1); L++, cur = next)
for (int i = max(L-n+1,0); i <= min(L,n-1); i++)
for (int j = i; j <= min(L,n-1); j++)
{ // max cherries for path length L-1 before arriving (i,k-1) and (j,k-j)
int curMax = max(max(Cur(i,j), Cur(i-1,j)), max(Cur(i,j-1),Cur(i-1,j-1)));
// max cherries for path length L reaching (i,k-1) and (j,k-j)
next[i][j] = (grid[i][L-i]>=0 && grid[j][L-j]>=0 && curMax>=0)? curMax+grid[i][L-i]+(i!=j)*grid[j][L-j] : -1;
}
return max(Cur(n-1,n-1), 0);
}
```