It is the same as two path start from (0, 0) to (n-1, n-1)

dp[x1][x2] means two length p path , currently one arrived at [..., x1] , the other is at [..., x2], the max value we can get

loop on length p, update max.

bottom to up, updated to use one n*n array.

```
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int N = grid.size();
int P_LEN = N + N - 1;
vector<vector<int> > dp = vector<vector<int>>(N, vector<int>(N, -1));
dp[0][0] = grid[0][0];
for (int p = 2; p <= P_LEN; p++) {//p is the length of the path
for (int x1 = N - 1; x1 >= 0; x1--) {
for (int x2 = x1; x2 >= 0; x2--) {
int y1 = p - 1 - x1;
int y2 = p - 1 - x2;
if (y1 < 0 || y2 < 0 || y1 >= N || y2 >= N)
continue;
if (grid[y1][x1] < 0 || grid[y2][x2] < 0) {
dp[x1][x2] = -1;
continue;
}
int best = -1, delta = grid[y1][x1];
if (x1 != x2)
delta += grid[y2][x2];
if (x1 > 0 && x2 > 0 && dp[x1 - 1][x2 - 1] >= 0) //from left left
best = max(best, dp[x1 - 1][x2 - 1] + delta);
if (x1 > 0 && y2 > 0 && dp[x1 - 1][x2] >= 0) //from left up
best = max(best, dp[x1 - 1][x2] + delta);
if (y1 > 0 && x2 > 0 && dp[x1][x2 - 1] >= 0) //from up left
best = max(best, dp[x1][x2 - 1] + delta);
if (y1 > 0 && y2 > 0 && dp[x1][x2] >= 0) //from up up
best = max(best, dp[x1][x2] + delta);
dp[x1][x2] = best;
}
}
}
return dp[N - 1][N - 1] < 0 ? 0 : dp[N - 1][N - 1];
}
};
```