Thanks for @storypku https://discuss.leetcode.com/topic/112877/annotated-c-dp-solution

and @jordandong

https://discuss.leetcode.com/topic/112856/c-dp-solution/2

who post their solutions.

And I was thinking about this problem for a whole afternoon and I just wanna add some comments from myself to better understand this problem.

At first I tried use DFS and separated the question into two parts: from [0,0] to [n-1,n-1] and from [n-1,n-1] to [0,0], but the time limit exceeded.

Some comments:

**n** is the side length of grid.

First of all, there are two phases, from [0,0] to [n-1,n-1] and from [n-1,n-1] to [0,0]. However, these two paths can be viewed both as from [0,0] to [n-1, n-1], because they are **"mirror systematic"**. What we want is finding out the **largest sum** of two traverses both from [0,0] and [n-1, n-1].

Therefore, we use a 2D vector **dp** to store the largest sum of two paths. dp[i][j] is not so easy to understand, so here I explain i and j as:

- i: the going-down steps of the first path
- j: the going-down steps of the second path

We also know the total steps from [0,0] to [n-1,n-1] is **2n - 2**. Suppose the current total steps for each of path are **len**, then

for i, the steps that it can go down is **min(n-1, len)**; the same for the j.

Once we give the current total steps of each path, the final position in the grid of each path can be confirmed, which are grid[i][len - i] and grid[j][len - j]. Therefore, if grid[i][len - i] is -1 or grid[j][len - j] is -1, we can skip and continue to the i++ or j++ in our for loop.

Each time we increase our total steps by 1, and consider all possible paths in the two "mirror systematic" paths,

Basic idea is:

**dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + grid[i][len-i] + grid[j][len-j]**

Always remember that in the dp, dp[i][j] is the largest sum of two paths (the collected cherries), i and j is the steps of going-down for the two paths separately. In the grid[i][len-i] is the current position of path i in the grid, because the current total steps is **len**. The same for grid[j][len-j].

The following procedures can be checked in the code.

```
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size();
if(n == 1) return grid[0][0];
int steps = 2*n - 2;
for(int len = 1; len <= steps; ++len){
vector<vector<int>> temp(n, vector<int>(n, -1));
for(int i = 0; i <= len && i < n; ++i){
for(int j = 0; j <= len && j < n; ++j){
if(grid[i][len -i] < 0 || grid[j][len - j] < 0) continue;
int cher = dp[i][j];
//three possible cases to reach current position in the two paths.
if(i > 0) cher = max(cher, dp[i-1][j]);
if(j > 0) cher = max(cher, dp[i][j-1]);
if(i > 0 && j > 0) cher = max(cher, dp[i-1][j-1]);
if(cher < 0) continue;
//if i and j are the same, it means i and j are in the same position in the grid.
cher += grid[i][len - i] + (i == j ? 0 : grid[j][len - j]);
temp[i][j] = cher;
}
}
dp = move(temp);
}
return max(dp[n-1][n-1], 0);
}
};
```